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 …

Boolean satisfiability (SAT) is arguably the quintessential NP-complete problem, believed to
be intractable in general. Yet, over the last two decades, engineers have designed and …

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 …

In recent years there has been an increasing interest in studying proof systems stronger than
Resolution, with the aim of building more efficient SAT solvers based on them. In defining …

This perspective piece calls for the study of the new field of Intersymbolic AI, by which we
mean the combination of symbolic AI, whose building blocks have inherent …

We show that for any integer d> 0, depth-d Frege systems are NP-hard to automate. Namely,
given a set S of depth-d formulas, it is NP-hard to find a depth-d Frege refutation of S in time …

Semialgebraic proof systems have been studied extensively in proof complexity since the
late 1990s to understand the power of Gröbner basis computations, linear and semidefinite …

Connections between proof complexity and circuit complexity have become major tools for
obtaining lower bounds in both areas. These connections-which take the form of …

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 …

The CDCL algorithm for SAT is equivalent to the resolution proof system under a few
assumptions, one of them being an optimal non-deterministic procedure for choosing the …