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. ред. / Monika Henzinger; David Kempe; Ilias Diakonikolas. Association for Computing Machinery, 2018. стр. 801-814 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Garg, A, Kamath, P, Göös, M & Sokolov, D 2018, Monotone circuit lower bounds from resolution. в M Henzinger, D Kempe & I Diakonikolas (ред.), 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, стр. 801-814, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, Соединенные Штаты Америки, 25/06/18. https://doi.org/10.1145/3188745.3188838

APA

Garg, A., Kamath, P., Göös, M., & Sokolov, D. (2018). Monotone circuit lower bounds from resolution. в M. Henzinger, D. Kempe, & I. Diakonikolas (Ред.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (стр. 801-814). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188838

Vancouver

Garg A, Kamath P, Göös M, Sokolov D. Monotone circuit lower bounds from resolution. в Henzinger M, Kempe D, Diakonikolas I, Редакторы, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2018. стр. 801-814. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/3188745.3188838

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. Редактор / Monika Henzinger ; David Kempe ; Ilias Diakonikolas. Association for Computing Machinery, 2018. стр. 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 -

ID: 52048100