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 …

We offer a new understanding of some aspects of practical SAT-solvers that are based on
DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a …

This note, based on my 4ECM lecture, exposes few basic points of proof complexity in a way
accessible to any mathematician. In many parts of mathematics one finds statements …

Propositional proof complexity is the study of the sizes of propositional proofs, and more
generally, the resources necessary to certify propositional tautologies. Questions about …

An active line of research in proof complexity over the last decade has been the study of
proof space and trade-offs between size and space. Such questions were originally …

This paper is intended as an informal and accessible survey of proof complexity for non-
experts, focusing on some comparatively weak proof systems of particular interest in …

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to
superlinear space. In particular, we show that there are formulas of size N that have …

Pebble games were extensively studied in the 1970s and 1980s in a number of different
contexts. The last decade has seen a revival of interest in pebble games coming from the …

The search of a precise measure of what hardness of SAT instances means for state-of-the-
art solvers is a relevant research question. Among others, the space complexity of treelike …

During the last 10 to 15 years, an active line of research in proof complexity has been to
study space complexity and time-space trade-offs for proofs. Besides being a natural …