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.


The book is mainly directed to:


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

Return to my home page