ECCC-Report TR08-080https://eccc.weizmann.ac.il/report/2008/080Comments and Revisions published for TR08-080en-usWed, 03 Dec 2008 00:00:00 +0200
Revision 1
| Random low degree polynomials are hard to approximate |
Ido Ben-Eliezer,
Rani Hod,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2008/080#revision1We 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.
Wed, 03 Dec 2008 00:00:00 +0200https://eccc.weizmann.ac.il/report/2008/080#revision1
Paper TR08-080
| Random low degree polynomials are hard to approximate |
Ido Ben-Eliezer,
Rani Hod,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2008/080We 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.
Wed, 10 Sep 2008 00:55:47 +0300https://eccc.weizmann.ac.il/report/2008/080