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.