Authors: James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich

Abstract: We consider the problem of approximating a Boolean function f : {0,1}ⁿ -> {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⁰ exponential-size lower bounds in a new way. This allows us to prove the new result that an AC⁰ circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.

Download Full Paper