**Title:** The Expressive Power of Voting Polynomials
**Authors:** James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich

**Abstract:**
We consider the problem of approximating a Boolean function *f* :
{0,1}^{n} -> {0,1} by the sign of an integer
polynomial *p* of degree *k*. For us, a polynomial
*p*(**x**) predicts the value of *f*(**x**) if,
whenever *p*(**x**) ≥ 0, *f*(**x**) = 1, and
whenever *p*(**x**) < 0, *f*(**x**) = 0. A
low-degree polynomial *p* is a good approximator for *f* if
it predicts *f* at almost all points. Given a positive integer
*k*, and a Boolean function *f*, we ask, ``how good is the
best degree *k* approximation to *f*?'' We introduce a new
lower bound technique which applies to any Boolean function. We show
that the lower bound technique yields tight bounds in the case
*f* is parity. Minsky and Papert proved that a perceptron can
not compute parity; our bounds indicate exactly how well a perceptron
can *approximate* it. As a consequence, we are able to give the
first correct proof that, for a random oracle *A*,
PP^{A} is properly contained in
PSPACE^{A}. We are also able to prove the old
AC^{0} exponential-size lower bounds in a new way. This
allows us to prove the new result that an AC^{0} circuit with
one majority gate cannot approximate parity. Our proof depends only
on basic properties of integer polynomials.

Download Full Paper