ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > KNESER GRAPH:
Reports tagged with Kneser graph:
TR05-021 | 14th February 2005
Stasys Jukna

Disproving the single level conjecture

Revisions: 2 , Comments: 1
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 ... more >>>



ISSN 1433-8092 | Imprint