One of these strands---*structural
complexity*---deals with high-level complexity questions: is space
a more powerful resource than time? Does randomness enhance the power
of efficient computation? Is it easier to verify a proof than to
construct one? So far we do not know the answers to any of these
questions; thus most results in structural complexity are
*conditional* results that rely on various unproven assumptions,
like P!=NP.

The second strand---*concrete complexity* or
*circuit complexity*---deals with establishing lower bounds on the
computational complexity of specific problems, like multiplication of
matrices or detecting large cliques in graphs. This is essentially a low-level
study of computation; it typically centers around particular models of
computation such as decision trees, branching programs, boolean formulas,
various classes of boolean circuits, communication protocols,
proof systems and the like.
This line of research aims to establish *unconditional* lower bounds,
which rely on no unproven assumptions.

This book is about the life on the second strand---circuit complexity---with
a special focus on *lower bounds*. It gives self-contained
proofs of a wide range of unconditional lower bounds for important models of
computation, covering many of the gems of the field that have been
discovered over the past several decades, right up to results from the
last year or two.
More than twenty years have passed since the well-known
books on circuit complexity by Savage (1976), Nigmatullin (1983),
Wegener (1987) and Dunne (1988) as well as a famous survey paper
of Boppana and Sipser (1990) were written.
I feel it is time to summarize the new developments in circuit complexity
during these two decades.

The book is mainly devoted to mathematicians wishing to get an idea of what is actually going on in this one of the hardest, but also mathematically cleanest fields of computer science, to researchers in computer science wishing to refresh their knowledge about the state of art in circuit complexity, as well as to students wishing to try their luck in circuit complexity.

I have highlighted some of the most important proof arguments for circuit lower
bounds, without trying to be
encyclopedic. To keep the length of the book within reasonable limits, I was forced
to focus on *classical* circuit models---results
on their randomized or algebraic versions receive less attention here.
Also, I often compromise the numerical tightness of results in favor of clarity
of argument.
My goal is to present the ``big picture'' of existing lower bound methods,
in the hope that the reader will be motivated to find new
ones. More than 40 open problems, marked as Research Problems, are mentioned
along the way. Most of them are of a combinatorial or combinatorial-algebraic flavor
and can be attacked by students with no background in computational complexity.

The book is meant to be approachable
for graduate students
in mathematics and computer science, and
is self-contained. The text assumes a certain mathematical
maturity but *no* special knowledge in
the theory of computing. For non-mathematicians,
all necessary mathematical background is collected
in the appendix of the book.
As in combinatorics or in number theory, the
models and problems in circuit complexity are usually quite easy
to state and explain, even for the layperson. Most often, their solution
requires a clever insight, rather than fancy mathematical tools.

I am grateful to
*Miklos Ajtai,
Marius Damarackas,
Andrew Drucker,
Anna G\'al,
Sergey Gashkov,
Dmitry Gavinsky,
Jonathan Katz,
Michal Koucky,
Matthias Krause,
Andreas Krebs,
Alexander Kulikov,
Meena Mahajan,
Igor Sergeev,
Hans Ulrich Simon,
Gy"orgy Tur'an,* and
*Sundar Vishwanathan*
for comments and corrections on the draft versions of the book.
Sergey Gashkov and Igor Sergeev also informed me about numerous results
available only in Russian.

I am especially thankful to
*Andrew Drucker,
William Gasarch,
Jonathan Katz,
Massimo Lauria,
Troy Lee,
Matthew Smedberg,
Ross Snider,
Marcos Villagra,*
and * Ryan Williams*
for proofreading parts of the book and giving very useful suggestions concerning the
contents.
Their help was crucial when putting the finishing touches to the manuscript.
The strong commitment of Andrew Drucker in organizing these final touches
and proofreading more than a half of the book by himself cannot
be acknowledged well enough.
All remaining errors are entirely my fault.
My sincere thanks to Georg Schnitger
for his support during my stay in Frankfurt.
Finally, I would like to acknowledge the German Research Foundation
(Deutsche Forschungsgemeinschaft)
for giving an opportunity to finish the book while working within the grant SCHN~503/5-1.

My deepest thanks to my wife, Daiva, and my daughter, Indre, for their patience.

S.J.

Frankfurt am Main/Vilnius, August 2011

Return to the home page of the book