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