Ido Ben-Eliezer, Rani Hod, Shachar Lovett

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