Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > QUADRATIC FUNCTIONS:
Reports tagged with quadratic functions:
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 ... more >>>




ISSN 1433-8092 | Imprint