Abstract
A polynomial P in F[X_1,...,X_n] is said to epsilonapproximate a
boolean function F:{0,1}^n > {0,1} under distribution D over {0,1}^n
if for a random x chosen according to distribution D, the probability
that P(x) is not equal to F(x) is at most epsilon. Smolensky (1987)
showed that for any constant distinct primes p and q, any polynomial P
in F_p[x_1,...,x_n] that (1/2q  Omega(1))approximates the boolean
function MOD_q:{0,1}^n>{0,1}  which accepts its input iff the
number of ones is nonzero modulo q  under the uniform distribution
must have degree Omega(n^{1/2}).
We consider the problem of finding an explicit function
f:{0,1}^n>{0,1} that has no epsilonapproximating polynomial of
degree less than n^{1/2 + Omega(1)} under *some distribution*, for
some constant epsilon>0. We show a number of negative results in this
direction: specifically, we show that many interesting classes of
functions including symmetric functions and linear threshold functions
do have approximating polynomials of degree O(n^{1/2+o(1)}) under
every distribution. This demonstrates the power of this model of
computation.
The above results, in turn, provide further motivation for this lower
bound question. Using the upper bounds obtained above, we show that
finding such a function f would have applications to: lower bounds for
AC^0 o F where F is the class of symmetric and threshold gates;
stronger lower bounds for 1round compression by ACC^0[p] circuits;
improved correlation lower bounds against low degree polynomials; and
(under further conditions) showing that the Inner Product (over F_2)
function does not have small AC^0 o MOD_2 circuits.
BibTeX  Entry
@InProceedings{srinivasan:LIPIcs:2013:4373,
author = {Srikanth Srinivasan},
title = {{On Improved Degree Lower Bounds for Polynomial Approximation}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {201212},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897644},
ISSN = {18688969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4373},
URN = {urn:nbn:de:0030drops43737},
doi = {10.4230/LIPIcs.FSTTCS.2013.201},
annote = {Keywords: Polynomials, Approximation, Compression, Circuit lower bounds}
}
Keywords: 

Polynomials, Approximation, Compression, Circuit lower bounds 
Collection: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) 
Issue Date: 

2013 
Date of publication: 

10.12.2013 