**Authors:** Richard Beigel

**Abstract:**
Suppose that a Boolean function *f* is computed by a constant
depth circuit with 2^{m} AND-, OR-, and NOT-gates &emdash;
and *m* majority-gates. We prove that *f* is computed by a
constant depth circuit with 2^{mO(1)} AND-,
OR-, and NOT-gates &emdash; and a single majority-gate, which is at the
root.

One consequence is that if a Boolean function *f* is computed by
an AC^{0} circuit plus polylog majority-gates, then *f*
is computed by a probabilistic perceptron having polylog order.
Another consequence is that if *f* agrees with the parity
function on three-fourths of all inputs, then *f* cannot be
computed by a constant depth circuit with
2^{no(1)} AND-, OR-, and NOT-gates, and
*n*^{o(1)} majority-gates.