When do extra majority gates help?
Richard Beigel · 1992
Suppose that f is computed by a constant depth circuit with 2m AND-, OR-, and NOT-gates, and m majority-gates. We prove that f is computed by a constant depth circuit with 2mo(1) AND-, OR-, and NOT-gates, and a single majority-gate, which is at the root.