Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-080 | 3rd December 2008 00:00

Random low degree polynomials are hard to approximate

RSS-Feed




Revision #1
Authors: Ido Ben-Eliezer, Rani Hod, Shachar Lovett
Accepted on: 3rd December 2008 00:00
Downloads: 4984
Keywords: 


Abstract:

We study the problem of how well a typical multivariate polynomial
can be approximated by lower degree polynomials over~$\F$. We prove
that, with very high probability, a random degree~$d+1$ polynomial
has only an exponentially small correlation with all polynomials of
degree~$d$, for all degrees~$d$ up to $\Theta(n)$. That is, a random
degree~$d+1$ polynomial does not admit a good approximation of lower
degree. In order to prove this, we provide far tail estimates on the
distribution of the bias of a random low degree polynomial.
Recently, several results regarding the weight distribution of
Reed--Muller codes were obtained. Our results can be interpreted as
a new large deviation bound on the weight distribution of
Reed--Muller codes.


Paper:

TR08-080 | 3rd July 2008 00:00

Random low degree polynomials are hard to approximate





TR08-080
Authors: Ido Ben-Eliezer, Rani Hod, Shachar Lovett
Publication: 10th September 2008 00:55
Downloads: 3053
Keywords: 


Abstract:

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.
We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to $\Theta(n)$.
That is, a random degree $d$ polynomial does not admit good approximations of lesser degree.

In order to prove this, we prove far tail estimates on the distribution of the bias of a random low degree polynomial.
As part of the proof, we also prove tight lower bounds on the dimension of truncated Reed--Muller codes.



ISSN 1433-8092 | Imprint