Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting
Planes proof system (CP) and the Lovász-Schrijver calculi (LS) utilizing linear, respectively …

We consider several problems related to the use of resolution-based methods for
determining whether a given boolean formula in conjunctive normal form is satisfiable. First …

The pigeonhole principle asserts that there is no injective mapping from m pigeons to n
holes as long as m> n. It is amazingly simple, expresses one of the most basic primitives in …

An exponential separation between regular and general resolution Page 1 An Exponential
Separation between Regular and General Resolution Michael Alekhnovich Department of …

This paper presents a translation-based resolution decision procedure for the multimodal
logic K (m)(∩,∪,⌣) defined over families of relations closed under intersection, union, and …

We investigate tradeoffs of various important complexity measures such as size, space and
width. We show examples of CNF formulas that have optimal proofs with respect to any one …

We prove exponential lower bounds on the size of a bounded depth Frege proof of a Tseitin
graph-based contradiction, whenever the underlying graph is an expander. This is the first …

We show that an LK proof of size m of a monotone sequent (a sequent that contains only
formulas in the basis∧,∨) can be turned into a proof containing only monotone formulas of …

Branch-and-cut methods are among the more successful techniques for solving integer
programming problems. They can also be used to prove that all solutions of an integer …

In this paper we develop a connection between optimal propositional proof systems and
structural complexity theory—specifically, there exists an optimal propositional proof system …