Under the auspices of the Computational Complexity Foundation (CCF)

ECCC BOOKS, LECTURES AND SURVEYS > ON LOWER BOUNDS FOR CIRCUITS AND SELECTION:

### Ulfberg, Stafan

Royal Institute of Technology
Stockholm, Sweden, 1999

## On Lower Bounds for Circuits and Selection

### Abstract

This thesis presents results on lower bounds for circuit complexity, implications of some of these bounds for relativized complexity, and lower bounds for median selection.

Boolean functions may be computed using circuits consisting of AND, OR, and NOT gates. The size of a circuit is the number of gates it contains, and the size of the smallest circuit computing a function is a measure of the function's complexity. The depth of a circuit is the number of gates on the longest path from any input to the output gate. Monotone circuits only contain AND and OR gates, and bounded depth circuits have a specified maximum allowed depth.

Razborov invented the method of approximation as a way of proving lower bounds for the size of monotone circuits. The method involves approximating the outputs of the gates in a circuit with DNF formulas with certain restrictions. We show how the method can be made more symmetric by using both CNF and DNF formulas. As a consequence we no longer need the Sunflower lemma that has been essential for the method of approximation. The new approximation argument corresponds to Haken's recent method for proving lower bounds for monotone circuit complexity (counting bottlenecks) in a natural way. We demonstrate the method by providing lower bounds for the BMS problem introduced by Haken, for Andreev's polynomial problem, and for Clique; the exponential bounds obtained are the same as the previously best known for the respective problems.

We also introduce a new function based on combinatorial designs, which is only partially explicit, and prove the lower bound 2^O(n^{1/3}) for this function. The new approximation argument is also extended to hold for monotone real circuits, which have gates that compute arbitrary real-valued monotone functions. For bounded depth circuits, we show that there are functions computable by linear size boolean circuits of depth $k$ that require super-polynomial size perceptrons of depth k-1, for k2$. Dor and Zwick have been able to extend these ideas to obtain a$(2{+}\epsilon)n$lower bound, for some tiny$\epsilon>0\$, on the number of comparisons performed, in the worst case, by any median selection algorithm.

Acknowledgments .....................................   v

1. Introduction .....................................   1
2. Models and Notation ..............................  17
3. Lower Bounds for Monotone Circuits................  25
4. A Lower Bound for Perceptrons ....................  51

5. Oracle Seperations ...............................  59
6. On Lower Bounds for Selecting the Median .........  69

Bibliography ........................................  80


ISSN 1433-8092 | Imprint