Abstract.
We consider the
minimal number of AND and OR gates in monotone circuits for quadratic
boolean functions,
i.e. disjunctions of length-2 monomials. The
single level conjecture claims that monotone single level circuits,
i.e. circuits which have only one level of AND gates, for quadratic
functions are not much larger than arbitrary
monotone circuits.
In this
paper we
disprove the conjecture: there are quadratic functions in n variables whose monotone circuits
have
size O(n) whereas their monotone single level circuits
require size Omega(n2/\log3 n).
.