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.
Další plán:
Roman Smolensky: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity
(referuje Michal Koucký)
