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 consider the range avoidance problem (called Avoid): given the description of a circuit
with more output gates than input gates, find a string that is not in the range of the circuit …

Hardness magnification reduces major complexity separations (such as EXP⊈ NC 1) to
proving lower bounds for some natural problem Q against weak circuit models. Several …

This article continues the development of hardness magnification, an emerging area that
proposes a new strategy for showing strong complexity lower bounds by reducing them to a …

We prove a new switching lemma that works for restrictions that set only a small fraction of
the variables and is applicable to formulas in disjunctive normal form (DNFs) with small …

We call a pseudorandom generator G_n:{0,1\}^n→{0,1\}^m hard for a propositional proof
system P if P cannot efficiently prove the (properly encoded) statement G_n(x_1,...,x_n)≠b …

We prove several results giving new and stronger connections between learning, circuit
lower bounds and pseudorandomness. Among other results, we show a generic learning …

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 …

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 …

This is a survey about the title question, written for people who (like the author) see logic as
forbidding, esoteric, and remote from their usual concerns. Beginning with a crash course on …