Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rani Hod:

TR08-080 | 3rd July 2008
Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Random low degree polynomials are hard to approximate

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint