TR96-004 Authors: Shiva Chaudhuri, Jaikumar Radhakrishnan

Publication: 18th January 1996 12:17

Downloads: 1089

Keywords:

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.