Over the last twenty years, an exciting interplay has emerged between proof systems and
algorithms. Some natural families of algorithms can be viewed as a generic translation from …

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 show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, It
is-hard to find a CP refutation of F in time polynomial in the length of the shortest such …

This is a survey of work on proof complexity and proof search from a logico-algorithmic
viewpoint, as motivated by the P versus NP problem. We discuss propositional proof …

We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is
NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali …

We study the problem of obtaining lower bounds for polynomial calculus (PC) and
polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al.'99] …

Algebraic proof systems, such as Polynomial Calculus (PC) and Polynomial Calculus with
Resolution (PCR), refute contradictions using polynomials. Space complexity for such …

We consider the graph $ k $-colouring problem encoded as a set of polynomial equations in
the standard way over $0/1$-valued variables. We prove that there are bounded-degree …

We obtain a streamlined proof of an important result by Alekhnovich and Razborov [Michael
Alekhnovich and Alexander A. Razborov, 2008], showing that it is hard to automatize both …

Guest Column Page 1 Guest Column: Proof Complexity and Beyond1 Alexander Razborov2
Abstract This essay is a highly personal and biased account of some main concepts and …