On the limits of gate elimination

Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov

Research outputpeer-review

2 Citations (Scopus)

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 186n-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.

Original languageEnglish
Title of host publication41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
EditorsAnca Muscholl, Piotr Faliszewski, Rolf Niedermeier
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770163
DOIs
Publication statusPublished - 1 Aug 2016
Event41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krakow
Duration: 22 Aug 201626 Aug 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume58
ISSN (Print)1868-8969

Conference

Conference41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
CountryPoland
CityKrakow
Period22/08/1626/08/16

    Fingerprint

Scopus subject areas

  • Software

Cite this

Golovnev, A., Hirsch, E. A., Knop, A., & Kulikov, A. S. (2016). On the limits of gate elimination. In A. Muscholl, P. Faliszewski, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 [46] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 58). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2016.46