On the limits of gate elimination

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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[Formula presented]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 a circuit by making one or several substitutions to the input variables and repeats this inductively. In this paper 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
Pages (from-to)107-119
Number of pages13
JournalJournal of Computer and System Sciences
Volume96
DOIs
StatePublished - 1 Sep 2018

Scopus subject areas

  • Computer Science (miscellaneous)
  • Theoretical Computer Science
  • Mathematics (miscellaneous)
  • Computational Theory and Mathematics

Keywords

  • Circuit complexity
  • Gate elimination
  • Lower bounds
  • LOWER BOUNDS
  • SIZE
  • BOOLEAN FUNCTIONS
  • CIRCUIT COMPLEXITY

Fingerprint

Dive into the research topics of 'On the limits of gate elimination'. Together they form a unique fingerprint.

Cite this