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.