Boolean Function Complexity: Advances and Frontiers

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

Readership

• 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

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.