Communication complexity is the mathematical study of scenarios where several parties
need to communicate to achieve a common goal, a situation that naturally appears during …

The width of a Resolution proof is defined to be the max. imal number of liter& in any clause
of the proof. In this paper we relate proof width to proof length (&size), in both general …

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 …

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing
the polynomial P using only additions and multiplications. It is a syntactic model of …

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 …

Monotone Boolean functions are an important object in discrete mathematics and
mathematical cybernetics. Topics related to these functions have been actively studied for …

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 …

We present the best known separation between tree-like and general resolution, improving
on the recent exp (n∈) separation of [2]. This is done by constructing a natural family of …

We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of
certain functions in models of parallel computation. We apply the tools to construct a class of …

We show that deterministic communication complexity can be super logarithmic in the
partition number of the associated communication matrix. We also obtain near-optimal …