Many Boolean functions have short representations by OBDDs (ordered binary decision diagrams) if appropriate variable orderings are used. For tree-like circuits, which may contain EXOR-gates, it is proved that some depth first traversal leads to an optimal variable ordering. Moreover, an optimal variable ordering and the resulting OBDD can be ... more >>>

Some operations over Boolean functions are considered. It is shown that the operation of the geometrical projection and the operation of the monotone extension can increase the complexity of Boolean functions for formulas in each finite basis, for switching networks, for branching programs, and read-$k$-times branching programs, where $k\ge 2$. ... more >>>

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation ... more >>>

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>>

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials. For every fixed ... more >>>