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 #1 to TR16-119 | 4th June 2020 05:58

On the Limits of Gate Elimination

RSS-Feed




Revision #1
Authors: Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov
Accepted on: 4th June 2020 05:58
Downloads: 656
Keywords: 


Abstract:

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 $3\frac1{86}n-o(n)$. All known lower bounds are based on the so-called gate elimination technique. A typical gate elimination argument shows that it is possible to eliminate several gates from an optimal circuit by making one or several substitutions to the input variables and repeats this inductively. In this note we prove that this method cannot achieve linear bounds of $cn$ beyond a certain constant $c$, where $c$ depends only on the number of substitutions made at a single step of the induction.



Changes to previous version:

Proved a limitation of the gate elimination method (with any subadditive measure) that performs almost the maximal N/2 substitutions. Added a lower bound on decision tree complexity.


Paper:

TR16-119 | 1st August 2016 18:51

On the Limits of Gate Elimination





TR16-119
Authors: Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov
Publication: 1st August 2016 19:13
Downloads: 2658
Keywords: 


Abstract:

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 $3\frac1{86}n-o(n)$. All known lower bounds are based on the so-called gate elimination technique. A typical gate elimination argument shows that it is possible to eliminate several gates from an optimal circuit by making one or several substitutions to the input variables and repeats this inductively. In this note we prove that this method cannot achieve linear bounds of $cn$ beyond a certain constant $c$, where $c$ depends only on the number of substitutions made at a single step of the induction.



ISSN 1433-8092 | Imprint