Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-175 | 20th April 2019 01:34

Monotone Circuit Lower Bounds from Resolution

RSS-Feed




Revision #1
Authors: Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Accepted on: 20th April 2019 01:34
Downloads: 1362
Keywords: 


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.



Changes to previous version:

Journal version, including a discussion of applications.


Paper:

TR17-175 | 13th November 2017 21:38

Monotone Circuit Lower Bounds from Resolution





TR17-175
Authors: Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Publication: 14th November 2017 05:01
Downloads: 3083
Keywords: 


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.



ISSN 1433-8092 | Imprint