1. Random low-degree polynomials are hard to approximate.
- Author
-
Ben-Eliezer, Ido, Hod, Rani, and Lovett, Shachar
- Subjects
RANDOM polynomials ,PROBABILITY theory ,COMPUTATIONAL complexity ,CODING theory ,LIMIT theorems ,ORTHOGONAL polynomials - Abstract
We study the problem of how well a typical multivariate polynomial can be approximated by lower-degree polynomials over $${\mathbb F}$$ . We prove that almost all degree d polynomials have only an exponentially small correlation with all polynomials of degree at most d − 1, for all degrees d up to Θ( n). That is, a random degree d polynomial does not admit a good approximation 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. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF