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