This chapter gives an overview of proof complexity and connections to SAT solving, focusing
on proof systems such as resolution, Nullstellensatz, polynomial calculus, and cutting planes …

It is well-known that Resolution proofs can be efficiently simulated by Sherali–Adams (SA)
proofs. We show, however, that any such simulation needs to exploit huge coefficients …

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 …

We use critical block sensitivity, a new complexity measure introduced by Huynh and
Nordström (STOC 2012), to study the communication complexity of search problems. To …

We show that deterministic communication complexity can be super logarithmic in the
partition number of the associated communication matrix. We also obtain near-optimal …

The proof system resolution over parities (Res (⊕)) operates with disjunctions of linear
equations (linear clauses) over GF (2); it extends the resolution proof system by …

Separations: We introduce a monotone variant of Xor-Sat and show it has exponential
monotone circuit complexity. Since Xor-Sat is in NC^ 2, this improves qualitatively on the …

We present CNFgen, a generator of combinatorial benchmarks in DIMACS and OPB format.
The proof complexity literature is a rich source not only of hard instances but also of …

We obtain the first true size-space trade-offs for the cutting planes proof system, where the
upper bounds hold for size and total space for derivations with constantsize coefficients, and …

We characterize the size of monotone span programs computing certain “structured”
boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula …