Abstract:
We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth $d$ with $S$ gates can be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where $\epsilon(d) = 4^{-d}$) of its input values. This implies a superlinear size lower bound for a large class of functions. As a consequence, we show that constant depth circuits of polynomial size are strictly more powerful than constant depth circuits of linear size. We give circuit constructions that show that the bound $O(S^{1-\epsilon(d)})$ is near optimal. We also study the complexity of computing threshold functions. The function $T^n_r$ has the value 1 iff at least $r$ of its inputs have the value 1. We show that a circuit computing $T^n_r$ has at least $\Omega(r^2 (\log n)/ \log r)$ gates, for $r \leq n^{1/3}$, improving previous bounds. We also show a trade-off between the number of gates and the number of wires in a threshold circuit, namely, a circuit with $G$ $(< n/2)$ gates and $W$ wires computing $T^n_r$ satisfies $W \geq \Omega(n r (\log n)/(\log (G/\log n)))$, showing that it is not possible to simultaneously optimize the number of gates and wires in a threshold circuit. Our bounds for threshold functions are based on a combinatorial lemma of independent interest.