Search

We consider Boolean circuits over {or, and, neg} with negations applied only to input variables. To measure the "amount of negation" in such circuits, we introduce the concept of their "negation width". In particular, a circuit computing a monotone Boolean function f(x_1,...,x_n) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w=0 are equivalent to monotone Boolean circuits, while those of negation width w=n have no restrictions. Our motivation is that already circuits of moderate negation width w=n^{epsilon} for an arbitrarily small constant epsilon>0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K=min{w^m,m^w}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.

It is known that, for every constant $kgeq 3$, the presence of a $k$-clique (a complete subgraph on $k$ vertices) in an $n$-vertex graph cannot be detected by a monotone boolean circuit using fewer than $Omega((n/log n)^k)$ gates. We show that, for every constant $k$, the presence of an $(n-k)$-clique in an $n$-vertex graph can be detected by a monotone circuit using only $O(n^2log n)$ gates. Moreover, if we allow unbounded fanin, then $O(log n)$ gates are enough.

We consider the power of single level circuits in the context of graph complexity. We first prove that the single level conjecture fails for fanin-$2$ circuits over the basis ${oplus,land,1}$. This shows that the (surpisingly tight) phenomenon, established by Mirwald and Schnorr (1992) for quadratic functions, has no analogon for graphs. We then show that the single level conjecture fails for unbounded fanin circuits over ${lor,land,1}$. This partially answers the question of Pudl'ak, R"odl and Savick'y (1986). We also prove that $Sigma_2 eq Pi_2$ in a restricted version of the hierarhy of communication complexity classes introduced by Babai, Frankl and Simon (1986). Further, we show that even depth-$2$ circuits are surprisingly powerful: every bipartite $n imes n$ graph of maximum degree $Delta$ can be represented by a monotone CNF with $O(Deltalog n)$ clauses. We also discuss a relation between graphs and $ACC$-circuits.