main-content

## Über dieses Buch

Boolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive description of basic lower bound arguments, covering many of the gems of this “complexity Waterloo” that have been discovered over the past several decades, right up to results from the last year or two. Many open problems, marked as Research Problems, are mentioned along the way. The problems are mainly of combinatorial flavor but their solutions could have great consequences in circuit complexity and computer science. The book will be of interest to graduate students and researchers in the fields of computer science and discrete mathematics.

## Inhaltsverzeichnis

### Chapter 1. Our Adversary: The Circuit

Abstract
Boolean (or switching) functions map each sequence of bits to a single bit 0 or 1. Bit 0 is usually interpreted as “false”, and bit 1 as “true”. The simplest of such functions are the product$$\rm{x\cdot y}$$, sum$$\rm{x\oplus y}$$ mod 2, non-exclusive Or $${x\vee y}$$, negation $$\neg x=1-x$$ The central problem of boolean function complexity—the lower bounds problem—is:
Stasys Jukna

### Chapter 2. Analysis of Boolean Functions

Abstract
We finish this introductory partwith some algebraic properties of boolean functions: their expression and approximation by polynomials. We will use these properties later to prove lower bounds for several circuit models. It is, however, convenient to have all these properties collected at one place. The impatient reader who wishes to begin proving lower bounds immediately may safely skip this section, and return later when the properties in question are used.
Stasys Jukna

### Chapter 3. Games on Relations

Abstract
The communication complexity of boolean functions is an information theoretic measure of their complexity. Besides its own importance, this measure is closely related to the computational complexity of functions: it corresponds to the smallest depth of circuits computing them. Thus, this measure can be used to prove circuit lower bounds. Communication complexity is appealing not only for its elegance and relation to circuit complexity, but also because its study involves the application of diverse tools from algebra, combinatorics and other fields of mathematics.
Stasys Jukna

### Chapter 4. Games on 0-1 Matrices

Abstract
We have already seen that communication complexity of relations captures the depth of circuits. Protocols in this case are trying to solve search problems. In this chapter we consider the communication complexity of decision problems.
Stasys Jukna

### Chapter 5. Multi-Party Games

Abstract
The rich mathematical theory of two-party communication naturally invites us to consider scenarios involving k > 2 players. In the simplest case, we have some function f(x)whose input x is decomposed into k equally-sized parts $$\rm x=\rm (x_{1},\,.\,.\,.\,,x_{k})$$. There are k players who wish to collaboratively evaluate a given function f on every input x. Each player has unlimited computational power and full knowledge of the function. As in the case of two players, the players are not adversaries—they help and trust each other. Depending on what parts of the input x each player can see, there are two main models of communication:
Stasys Jukna

### Chapter 6. Formulas

Abstract
Although for general non-monotone circuits no super-linear lower bounds are known, the situation for formulas is somewhat better: here we are able to prove quadratic and even super-quadratic lower bounds. These bounds are achieved using remarkably different arguments: counting, random restrictions, set covering and graph entropy.
Stasys Jukna

### Chapter 7. Monotone Formulas

Abstract
We have seen that proving lower bound for general circuits is a very difficult task. Thus it is natural to try to obtain large lower bounds for a more restricted class of circuits, the class of monotone circuits. Monotone circuits consist only of AND and OR gates and have no NOT gates. Of course, such circuits cannot compute all boolean functions.
Stasys Jukna

### Chapter 8. Span Programs

Abstract
In 1993 Karchmer and Wigderson introduced an interesting linear algebraic model for computing boolean functions—the span program. A span program is just a matrix over some field with rows labeled by literals. (In this chapter we will only work over the field GF(2), but the results hold for any field.) The span program accepts an input assignment if and only if the all-1 vector can be obtained as a linear combination of the rows whose labels are satisfied by the input. The size of the span program is the number of rows in the matrix. A span program is monotone if only positive literals are used as labels of the rows, that is, negated variables are not allowed.
Stasys Jukna

### Chapter 9. Monotone Circuits

Abstract
We now consider monotone circuits, that is, circuits with fanin-2 AND and OR gates. As monotone formulas, such circuits can only compute monotone boolean functions.
Stasys Jukna

### Chapter 10. The Mystery of Negations

Abstract
The main difficulty in proving nontrivial lower bounds on the size of circuits using AND, OR and NOT is the presence of NOT gates—we already know how to prove even exponential lower bounds for monotone functions if no NOT gates are allowed.
Stasys Jukna

### Chapter 11. Depth-3 Circuits

Abstract
We consider boolean circuits with unbounded-fanin AND and OR gates. Inputs are variables and their negations. Conjunctive and disjunctive normal forms are such circuits of depth two, and exponential lower bounds for them are easy to prove.
Stasys Jukna

### Chapter 12. Large-Depth Circuits

Abstract
We now consider circuits of depth d ≥ 3. Out of attempts to prove lower bounds for such circuits, two powerful methods emerged. The first is a “depth reduction” argument: One tries to reduce the depth one layer at a time, until a circuit of depth 2 (or depth 1) remains. The key is the so-called Switching Lemma,which allows us to replace CNFs on the first two layers by DNFs, thus reducing the depth by 1.1
Stasys Jukna

### Chapter 13. Circuits with Arbitrary Gates

Abstract
In this chapter we consider unbounded-fanin circuits with arbitrary boolean functions as gates. The size of such a circuit is defined as the total number of wires (rather than gates) it has.
Stasys Jukna

### Chapter 14. Decision Trees

Abstract
A decision tree is an algorithm for computing a function of an unknown input. Each node of the tree is labeled by a variable and the branches from that node are labeled by the possible values of the variable. The leaves are labeled by the output of the function. The process starts at the root, knowing nothing, works down the tree, choosing to learn the values of some of the variables based on those already known and eventually reaches a decision. The decision tree complexity of a function is the minimum depth of a decision tree that computes that function.
Stasys Jukna

### Chapter 15. General Branching Programs

Abstract
A branching program is a generalization of a decision tree where the underlying graph can be an arbitrary directed acyclic graph. The model of branching programs is one of the most fundamental sequential (in contrast to parallel, as circuits or formulas) model of computations. This model captures in a natural way the deterministic space whereas nondeterministic branching programs do the same for the nondeterministic mode of computation.
Stasys Jukna

### Chapter 16. Bounded Replication

Abstract
Since, so far, we are unable to prove exponential lower bounds for general branching programs, it is natural to try to do this for restricted programs. We have seen that restricting the width of a program does not decrease their power too much: the resulting class of programs is almost as powerful at that of (unrestricted) formulas.
Stasys Jukna

### Chapter 17. Bounded Time

Abstract
In this chapter we show a time-size tradeoff for nondeterministic branching programs. By the size of a program in this chapter we will mean the number of nodes, not just the number of labeled edges. A program computes a given function in time T if every accepted input has at least one accepting computation of length at most T.
Stasys Jukna

### Chapter 18. Resolution

Abstract
Propositional proof systems operate with boolean formulas, the simplest of which are clauses, that is, ORs of literals, where each literal is either a variable $${x}_{i}$$ or its negation $$\Gamma{x}_{i}$$.A truth-assignment is an assignment of constants 0 and 1 to all the variables. Such an assignment satisfies (falsifies) a clause if it evaluates at least one (respectively, none) of its literals to 1.
Stasys Jukna

### Chapter 19. Cutting Plane Proofs

Abstract
We now turn our attention to a proof system more powerful than resolution—the so-called cutting plane proof system. This proof system, which can be viewed as a “geometric generalization” of resolution, originated in works on integer programming by Gomory (1963) and Chvátal (1973); as a proof system it was first considered in Cook et al. (1987) The basic idea is to use a few elementary rules to prove that a given system of linear inequalities (or “cutting planes”) with integer coefficients does not have a 0-1 solution.
Stasys Jukna

### Chapter 20. Epilogue

Abstract
The lower-bounds arguments we presented in this book work well for different restricted circuit classes but, so far, have not led to a non-linear lower bound for unrestricted circuits. In this concluding chapter we sketch several general results explaining this failure (the phenomenon of “natural proofs”) as well as showing a possible line of further attacks (the “fusion method”, indirect arguments).
Stasys Jukna

### Backmatter

Weitere Informationen