2026-08-17T12:48:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6459 2024-03-06T10:38:20Z ddc:004 open_access

On the Limits of Gate Elimination Golovnev, Alexander Hirsch, Edward A. Knop, Alexander Kulikov, Alexander S. circuit complexity lower bounds gate elimination 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 1/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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Golovnev and Edward A. Hirsch and Alexander Knop and Alexander S. Kulikov 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.46 urn:nbn:de:0030-drops-64593 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.46 eng https://creativecommons.org/licenses/by/3.0/legalcode