Standard
On the limits of gate elimination. / Golovnev, Alexander; Hirsch, Edward A.; Knop, Alexander; Kulikov, Alexander S.
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. ред. / Anca Muscholl; Piotr Faliszewski; Rolf Niedermeier. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. 46 (Leibniz International Proceedings in Informatics, LIPIcs; Том 58).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Golovnev, A
, Hirsch, EA, Knop, A
& Kulikov, AS 2016,
On the limits of gate elimination. в A Muscholl, P Faliszewski & R Niedermeier (ред.),
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016., 46, Leibniz International Proceedings in Informatics, LIPIcs, Том. 58, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Krakow, Польша,
22/08/16.
https://doi.org/10.4230/LIPIcs.MFCS.2016.46APA
Golovnev, A.
, Hirsch, E. A., Knop, A.
, & Kulikov, A. S. (2016).
On the limits of gate elimination. в A. Muscholl, P. Faliszewski, & R. Niedermeier (Ред.),
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 [46] (Leibniz International Proceedings in Informatics, LIPIcs; Том 58). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
https://doi.org/10.4230/LIPIcs.MFCS.2016.46Vancouver
Golovnev A
, Hirsch EA, Knop A
, Kulikov AS.
On the limits of gate elimination. в Muscholl A, Faliszewski P, Niedermeier R, Редакторы, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. 46. (Leibniz International Proceedings in Informatics, LIPIcs).
https://doi.org/10.4230/LIPIcs.MFCS.2016.46Author
Golovnev, Alexander
; Hirsch, Edward A. ; Knop, Alexander
; Kulikov, Alexander S. /
On the limits of gate elimination. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Редактор / Anca Muscholl ; Piotr Faliszewski ; Rolf Niedermeier. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. (Leibniz International Proceedings in Informatics, LIPIcs).
BibTeX
@inproceedings{ed521f27a1b14c8ea75b9f2d23693a5f,
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 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.",
keywords = "Circuit complexity, Gate elimination, Lower bounds",
author = "Alexander Golovnev and Hirsch, {Edward A.} and Alexander Knop and Kulikov, {Alexander S.}",
year = "2016",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.MFCS.2016.46",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Anca Muscholl and Piotr Faliszewski and Rolf Niedermeier",
booktitle = "41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016",
address = "Germany",
note = "41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 ; Conference date: 22-08-2016 Through 26-08-2016",
}
RIS
TY - GEN
T1 - On the limits of gate elimination
AU - Golovnev, Alexander
AU - Hirsch, Edward A.
AU - Knop, Alexander
AU - Kulikov, Alexander S.
PY - 2016/8/1
Y1 - 2016/8/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 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.
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 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.
KW - Circuit complexity
KW - Gate elimination
KW - Lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85012924592&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2016.46
DO - 10.4230/LIPIcs.MFCS.2016.46
M3 - Conference contribution
AN - SCOPUS:85012924592
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
A2 - Muscholl, Anca
A2 - Faliszewski, Piotr
A2 - Niedermeier, Rolf
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Y2 - 22 August 2016 through 26 August 2016
ER -
