The expressive power of voting polynomials (Q1330793)

A new lower bound technique for Boolean circuits is presented where polynomials over the rationals are used to describe (viz., to approximate) Boolean functions. The degree of the polynomial is related to the accurately of the approximation. Techniques to handle symmetric functions are derived. This yields lower bounds for circuits of And and Or gates with unbounded fan-in and one majority gate. The method is powerful enough to derive the known \(\text{AC}^0\) exponential-size lower bound for computing the parity function (du to Furst, Saxe, and Sipser) and to separate the complexity classes PP and PSPACE relative to a random oracle. A connection to voting puzzles establishes the power of the voting concept.