Theory of Computing
-------------------
Title : Monotone Circuit Lower Bounds from Resolution
Authors : Ankit Garg, Mika Goos, Pritish Kamath, and Dmitry Sokolov
Volume : 16
Number : 13
Pages : 1-30
URL : http://www.theoryofcomputing.org/articles/v016a013
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.
------------
An extended abstract of this paper appeared in the Proceedings of the
50th Symposium on Theory of Computing (STOC'18).