We introduce the notion of natural proof. We argue that the known proofs of lower bounds on
the complexity of explicit Boolean functions in non-monotone models fall within our definition …

Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …

We prove an exponential lower bound on the length of cutting plane proofs. The proof uses
an extension of a lower bound for monotone circuits to circuits which compute with real …

This book presents an up-to-date, unified treatment of research in bounded arithmetic and
complexity of propositional logic with emphasis on independence proofs and lower bound …

From the winner of the Turing Award and the Abel Prize, an introduction to computational
complexity theory, its connections and interactions with mathematics, and its central role in …

A proof of the (propositional) Craig interpolation theorem for cut-free sequent calculus yields
that a sequent with a cut-free proof (or with a proof with cut-formulas of restricted form; in …

We prove tight lower bounds, of up to n/sup/spl epsiv//, for the monotone depth of functions
in monotone-P. As a result we achieve the separation of the following classes. 1. Monotone …

Proof complexity, the study of the lengths of proofs in propositional logic, is an area of study
that is fundamentally connected both to major open questions of computational complexity …

In this chapter we shall consider the problem of determining the minimal complexity of a
proof of a theorem in a given proof system. We shall deal with propositional logic and first …

Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task
and usually undertaken on a case-by-case basis. We initiate a more systematic approach …