# The expressive power of voting polynomials

James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich.
The expressive power of voting polynomials.
*Combinatorica* 14(2):1–14, 1994. An earlier version appeared in
*Twenty-Third Annual ACM Symposium on Theory of Computing*,
May 1991, pp. 402–409.

## 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 AC0 exponential-size
lower bounds in a new way. This allows us to prove
the new result that an AC0 circuit with one majority
gate cannot approximate parity.
Our proof depends only on basic properties
of integer polynomials.

## BibTeX

Download@article(AspnesBFR1994,
title="The expressive power of voting polynomials",
author="James Aspnes and Richard Beigel and Merrick Furst and Steven Rudich",
journal="Combinatorica",
volume=14,
number=2,
pages={1--14},
year=1994
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page