Title: When do Extra Majority Gates Help? Polylog(n) Majority Gates are Equivalent to One

Authors: Richard Beigel

Abstract: Suppose that a Boolean function f is computed by a constant depth circuit with 2m AND-, OR-, and NOT-gates &emdash; and m majority-gates. We prove that f is computed by a constant depth circuit with 2mO(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 AC0 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 2no(1) AND-, OR-, and NOT-gates, and no(1) majority-gates.

Download Full Paper