Standard

Lower bounds for unrestricted boolean circuits : Open problems. / Kulikov, Alexander S.

Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings. ed. / Vladimir V. Podolskii; Fedor V. Fomin. Springer Nature, 2018. p. 15-22 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10846 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Kulikov, AS 2018, Lower bounds for unrestricted boolean circuits: Open problems. in VV Podolskii & FV Fomin (eds), Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10846 LNCS, Springer Nature, pp. 15-22, 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russian Federation, 6/06/18. https://doi.org/10.1007/978-3-319-90530-3_2

APA

Kulikov, A. S. (2018). Lower bounds for unrestricted boolean circuits: Open problems. In V. V. Podolskii, & F. V. Fomin (Eds.), Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings (pp. 15-22). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10846 LNCS). Springer Nature. https://doi.org/10.1007/978-3-319-90530-3_2

Vancouver

Kulikov AS. Lower bounds for unrestricted boolean circuits: Open problems. In Podolskii VV, Fomin FV, editors, Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings. Springer Nature. 2018. p. 15-22. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-90530-3_2

Author

Kulikov, Alexander S. / Lower bounds for unrestricted boolean circuits : Open problems. Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings. editor / Vladimir V. Podolskii ; Fedor V. Fomin. Springer Nature, 2018. pp. 15-22 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{0da10cd36da442e1a9afa24573641df1,
title = "Lower bounds for unrestricted boolean circuits: Open problems",
abstract = "To prove that P ≠ NP, it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds. In this note, we briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).",
author = "Kulikov, {Alexander S.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-90530-3_2",
language = "English",
isbn = "9783319905297",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "15--22",
editor = "Podolskii, {Vladimir V.} and Fomin, {Fedor V.}",
booktitle = "Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings",
address = "Germany",
note = "13th International Computer Science Symposium in Russia, CSR 2018 ; Conference date: 06-06-2018 Through 10-06-2018",

}

RIS

TY - GEN

T1 - Lower bounds for unrestricted boolean circuits

T2 - 13th International Computer Science Symposium in Russia, CSR 2018

AU - Kulikov, Alexander S.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - To prove that P ≠ NP, it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds. In this note, we briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).

AB - To prove that P ≠ NP, it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds. In this note, we briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).

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

U2 - 10.1007/978-3-319-90530-3_2

DO - 10.1007/978-3-319-90530-3_2

M3 - Conference contribution

AN - SCOPUS:85048046140

SN - 9783319905297

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 15

EP - 22

BT - Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings

A2 - Podolskii, Vladimir V.

A2 - Fomin, Fedor V.

PB - Springer Nature

Y2 - 6 June 2018 through 10 June 2018

ER -

ID: 49820627