
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.
voting puzzles, Switching theory, application of Boolean algebra; Boolean functions, Complexity classes (hierarchies, relations among complexity classes, etc.), General harmonic expansions, frames, Boolean functions, Orthogonal polynomials (combinatorics), Boolean circuits
voting puzzles, Switching theory, application of Boolean algebra; Boolean functions, Complexity classes (hierarchies, relations among complexity classes, etc.), General harmonic expansions, frames, Boolean functions, Orthogonal polynomials (combinatorics), Boolean circuits
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 106 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
