### 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.

### Table of Contents

**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 **