Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR05-021 | 28th November 2005 00:00

Disproving the single level conjecture

RSS-Feed




Revision #2
Authors: Stasys Jukna
Accepted on: 28th November 2005 00:00
Downloads: 1188
Keywords: 


Abstract:


Revision #1 to TR05-021 | 13th September 2005 00:00

Disproving the single level conjecture





Revision #1
Authors: Stasys Jukna
Accepted on: 13th September 2005 00:00
Downloads: 1095
Keywords: 


Abstract:


Paper:

TR05-021 | 14th February 2005 00:00

Disproving the single level conjecture





TR05-021
Authors: Stasys Jukna
Publication: 14th February 2005 13:26
Downloads: 1302
Keywords: 


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

Single level conjecture fails also for unbounded fanin circuits





Comment #1
Authors: Stasys Jukna
Accepted on: 2nd March 2006 16:20
Downloads: 652
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint