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       : https://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).