Standard

On the limits of gate elimination. / Golovnev, Alexander; Hirsch, Edward A.; Knop, Alexander; Kulikov, Alexander S.

In: Journal of Computer and System Sciences, Vol. 96, 01.09.2018, p. 107-119.

Research output: Contribution to journal › Article › peer-review

Harvard

Golovnev, A, Hirsch, EA, Knop, A & Kulikov, AS 2018, 'On the limits of gate elimination', Journal of Computer and System Sciences, vol. 96, pp. 107-119. https://doi.org/10.1016/j.jcss.2018.04.005

APA

Golovnev, A., Hirsch, E. A., Knop, A., & Kulikov, A. S. (2018). On the limits of gate elimination. Journal of Computer and System Sciences, 96, 107-119. https://doi.org/10.1016/j.jcss.2018.04.005

Vancouver

Golovnev A, Hirsch EA, Knop A, Kulikov AS. On the limits of gate elimination. Journal of Computer and System Sciences. 2018 Sep 1;96:107-119. https://doi.org/10.1016/j.jcss.2018.04.005

Author

Golovnev, Alexander ; Hirsch, Edward A. ; Knop, Alexander ; Kulikov, Alexander S. / On the limits of gate elimination. In: Journal of Computer and System Sciences. 2018 ; Vol. 96. pp. 107-119.

BibTeX

@article{ac4aed40ffe343e182715c96bbd63534,
title = "On the limits of gate elimination",
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.",
keywords = "Circuit complexity, Gate elimination, Lower bounds, LOWER BOUNDS, SIZE, BOOLEAN FUNCTIONS, CIRCUIT COMPLEXITY",
author = "Alexander Golovnev and Hirsch, {Edward A.} and Alexander Knop and Kulikov, {Alexander S.}",
year = "2018",
month = sep,
day = "1",
doi = "10.1016/j.jcss.2018.04.005",
language = "English",
volume = "96",
pages = "107--119",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On the limits of gate elimination

AU - Golovnev, Alexander

AU - Hirsch, Edward A.

AU - Knop, Alexander

AU - Kulikov, Alexander S.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - 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.

AB - 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.

KW - Circuit complexity

KW - Gate elimination

KW - Lower bounds

KW - LOWER BOUNDS

KW - SIZE

KW - BOOLEAN FUNCTIONS

KW - CIRCUIT COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85047540472&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2018.04.005

DO - 10.1016/j.jcss.2018.04.005

M3 - Article

AN - SCOPUS:85047540472

VL - 96

SP - 107

EP - 119

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -

ID: 36312452