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.

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.