Boolean Function Complexity: Advances and Frontiers
by Stasys Jukna
Research in circuit complexity began about 60 years ago with the seminal work of Claude Shannon. After many great initial results, progress has slowed down in the last 25 years. The discovery of serious barriers, like "natural proofs", has shown that complexity problems like P versus NP cannot (apparently) be solved by proving circuit lower bounds. This created an impression that circuit complexity is the ``complexity Waterloo.'' But this impression is not quite correct: the separation of P and NP is not the main goal of circuit complexity, and there still have been numerous advances in proving circuit lower bounds for various restricted circuit models, using a range of techniques from combinatorics, algebra, analysis, and other branches of mathematics.
The goals of circuit complexity are much more prosaic, "low level" complexity questions: to understand how circuits compute, to develop mathematical machinery for the analysis of circuits, and to create a mathematical toolbox against our adversary--the circuit. Toward these goals substantial progress has been made over the years. This book summarizes the main achievements in circuit complexity covering many "gems" of the field that have been discovered over the past several decades, right up to results from the last year or two.
Reasons for writing
Two decades have passed since the well known books on circuit complexity of Savage (1976), Nigmatullin (1983), Wegener (1987) and Dunne (1988), as well as a famous survey paper of Boppana and Sipser (1990), were written. It is time to summarize the developments in circuit complexity over these years.
Readership
The book is mainly directed to:
- Mathematicians wishing to get an idea on what is actually going on in this one of the hardest and mathematically "cleanest" fields of computer science with its many purely mathematical (mainly -combinatorial) problems whose solution would have great consequences in circuit complexity.
- Computer scientists wishing to refresh their knowledge in circuit complexity, to see in one place what happened in this field during the last two decades, as well as (and, perhaps, mainly) to
- Graduate and PhD students in mathematics and computer science wishing to try their power in this ``complexity Waterloo''.
Level
The text is meant to be approachable for graduate students in mathematics and computer science, and is self-contained. It assumes a certain mathematical maturity but no special knowledge in theory of computing. Necessary mathematical background and used notation is collected in the appendix of the book. The book can be used for a graduate course on circuit complexity or as a supplement material in a more general course on computational complexity. Many open problems, marked as ``Research Problems,'' are mentioned along the way.
Some Features
- It is the first book covering the happening in Circuit
Complexity during the past 20 years. It complements excellent books in
- Communication Complexity:
- Eyal Kushilevitz and Noam Nisan, "Communication Complexity," Cambridge University Press, 1997
- Structural Complexity:
- Oded Goldreich, "Computational Complexity: A Conceptual Perspective",
Cambridge University Press, 2008.
- Sanjeev Arora and Boaz Barak, "Computational Complexity: A Modern Approach",
Cambridge University Press, 2009.
- The book also includes some topics, like graph complexity or method of
finite limits, that are not known well enough even for specialists.
- Gives full and intuitive proofs of basic lower bounds, the stress is on
proof arguments rather than on resulting numerical bounds.
- Gives new proofs of classical results, like lower bounds for
monotone circuits, monotone span programs and constant-depth circuits.
- Presents some topics never touched in existing complexity books, like
graph complexity, span programs, bounds on the number of NOT gates,
bounds on Chvatal rank, lower bounds for
circuits with arbitrary boolean functions as gates, etc.
- Discusses results that are only available in Russian.
- Relates the circuit complexity with one of the ``hottest''
nowadays topics -- the proof complexity.
Return to my home page