Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LINEAR BOUNDS:
Reports tagged with linear bounds:
TR16-119 | 1st August 2016
Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

On the Limits of Gate Elimination

Revisions: 1

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>




ISSN 1433-8092 | Imprint