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.