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, PPA is properly contained in PSPACEA. 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