Jan Johannsen

Using a notion of real communication complexity recently

introduced by J. Krajicek, we prove a lower bound on the depth of

monotone real circuits and the size of monotone real formulas for

st-connectivity. This implies a super-polynomial speed-up of dag-like

over tree-like Cutting Planes proofs.

Albert Atserias, Maria Luisa Bonet, Jordi Levy

We study the Chv\'atal rank of polytopes as a complexity measure of

unsatisfiable sets of clauses. Our first result establishes a

connection between the Chv\'atal rank and the minimum refutation

length in the cutting planes proof system. The result implies that

length lower bounds for cutting planes, or even for ...
more >>>

Arist Kojevnikov

We continue a study initiated by Krajicek of

a Resolution-like proof system working with clauses of linear

inequalities, R(CP). For all proof systems of this kind

Krajicek proved an exponential lower bound that depends

on the maximal absolute value of coefficients in the given proof and

the maximal clause width.

Ran Raz, Iddo Tzameret

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>>

Massimo Lauria

Ramsey Theorem is a cornerstone of combinatorics and logic. In its

simplest formulation it says that there is a function $r$ such that

any simple graph with $r(k,s)$ vertices contains either a clique of

size $k$ or an independent set of size $s$. We study the complexity

of proving upper ...
more >>>

Pavel Hrubes

We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system.

We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two ... more >>>

Nicola Galesi, Pavel Pudlak, Neil Thapen

We study the space complexity of the cutting planes proof system, in which the lines in a proof are integral linear inequalities. We measure the space used by a refutation as the number of inequalities that need to be kept on a blackboard while verifying it. We show that any ... more >>>

Alexander Razborov

In this paper we initiate the study of width in semi-algebraic proof systems

and various cut-based procedures in integer programming. We focus on two

important systems: Gomory-Chv\'atal cutting planes and

Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for

proving width lower bounds and apply them to random $k$-CNFs and several ...
more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>>

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by

branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ...
more >>>

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>>

Leroy Chew

Quantified Boolean Formulas (QBFs) extend propositional formulas with Boolean quantifiers. Working with QBF differs from propositional logic in its quantifier handling, but as propositional satisfiability (SAT) is a subproblem of QBF, all SAT hardness in solving and proof complexity transfers to QBF. This makes it difficult to analyse efforts dealing ... more >>>

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

Susanna de Rezende, Jakob Nordström, Marc Vinyals

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 constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>

Jacobo Toran, Florian Wörz

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>

Dmitry Sokolov

The random $\Delta$-CNF model is one of the most important distribution over $\Delta\text{-}\mathrm{SAT}$ instances. It is closely connected to various areas of computer science, statistical physics, and is a benchmark for satisfiability algorithms. Fleming, Pankratov, Pitassi, and Robere and independently Hrubes and Pudlak showed that when $\Delta = \Theta(\log n)$, ... more >>>

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>