REPORTS > DETAIL:
Revision(s):
Abstract:
Abstract:
Paper:
TR05-021 | 14th February 2005 00:00
Disproving the single level conjecture
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 linear size whereas their monotone single level circuits require size $\Omega(n^{2-\epsilon})$.
Comment(s):
Comment #1 to TR05-021 | 2nd March 2006 16:20
Abstract:
Single level conjecture fails also for unbounded fanin circuits
Abstract: