Standard
Monotone circuit lower bounds from resolution. / Garg, Ankit; Kamath, Pritish; Göös, Mika; Sokolov, Dmitry.
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. Association for Computing Machinery, 2018. p. 801-814 (Proceedings of the Annual ACM Symposium on Theory of Computing).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Garg, A, Kamath, P, Göös, M
& Sokolov, D 2018,
Monotone circuit lower bounds from resolution. in M Henzinger, D Kempe & I Diakonikolas (eds),
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 801-814, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States,
25/06/18.
https://doi.org/10.1145/3188745.3188838APA
Garg, A., Kamath, P., Göös, M.
, & Sokolov, D. (2018).
Monotone circuit lower bounds from resolution. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.),
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 801-814). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery.
https://doi.org/10.1145/3188745.3188838Vancouver
Author
Garg, Ankit ; Kamath, Pritish ; Göös, Mika
; Sokolov, Dmitry. /
Monotone circuit lower bounds from resolution. STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. editor / Monika Henzinger ; David Kempe ; Ilias Diakonikolas. Association for Computing Machinery, 2018. pp. 801-814 (Proceedings of the Annual ACM Symposium on Theory of Computing).
BibTeX
@inproceedings{9d84a1bad14f4da1afa27e5bd4c1b37c,
title = "Monotone circuit lower bounds from resolution",
abstract = "For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols—or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.",
keywords = "Circuit complexity, Proof complexity",
author = "Ankit Garg and Pritish Kamath and Mika G{\"o}{\"o}s and Dmitry Sokolov",
year = "2018",
month = jun,
day = "20",
doi = "10.1145/3188745.3188838",
language = "English",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "801--814",
editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",
booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",
address = "United States",
note = "50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",
}
RIS
TY - GEN
T1 - Monotone circuit lower bounds from resolution
AU - Garg, Ankit
AU - Kamath, Pritish
AU - Göös, Mika
AU - Sokolov, Dmitry
PY - 2018/6/20
Y1 - 2018/6/20
N2 - For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols—or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.
AB - For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols—or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.
KW - Circuit complexity
KW - Proof complexity
UR - http://www.scopus.com/inward/record.url?scp=85049886695&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188838
DO - 10.1145/3188745.3188838
M3 - Conference contribution
AN - SCOPUS:85049886695
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 801
EP - 814
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Henzinger, Monika
A2 - Kempe, David
A2 - Diakonikolas, Ilias
PB - Association for Computing Machinery
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -
