Random low degree polynomials are hard to approximate
by Ido Ben Eliezer, Rani Hod and Shachar Lovett
Oded's comments
This work shows that almost all degree $d+1$ polynomials over GF(2)
are extremely hard to approximate by degree $d$ polynomials;
that is, the correlation is exponentially vanishing in the number
of variables.
To me this sounds as a very natural and/or basic result
in the context of arithmetic complexity.
The original abstract
We study the problem of how well a typical multivariate polynomial can be
approximated by lower degree polynomials over the field F_2.
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 good approximations
of lower degree.
In order to prove this, we prove 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.
Back to
list of Oded's choices.