Worst Case to Average Case Reductions for Polynomials

Abstract

A degree-$d$ polynomial $p$ in $n$ variables over a field $\F$ is {\em equidistributed} if it takes on each of its $|\F|$ values close to equally often, and {\em biased} otherwise. We say that $p$ has a {\em low rank} if it can be expressed as a bounded combination of polynomials of lower degree. Green and Tao [gt07] have shown that bias imply low rank over large fields (i.e. for the case $d < |\F|$). They have also conjectured that bias imply low rank over general fields. In this work we affirmatively answer their conjecture. Using this result we obtain a general worst case to average case reductions for polynomials. That is, we show that a polynomial that can be {\em approximated} by few polynomials of bounded degree, can be {\em computed} by few polynomials of bounded degree. We derive some relations between our results to the construction of pseudorandom generators, and to the question of testing concise representations.

Cited by in corpus (9)

• Fourier sparsity, spectral norm, and the Log-rank conjecture
• The List-Decoding Size of Reed-Muller Codes
• Extending weakly polynomial functions from high rank varieties
• Relative Rank and Regularization
• Higher-order Fourier analysis of ${\mathbb{F}}_p^n$ and the complexity of systems of linear forms
• The density of weights of Generalized Reed--Muller codes
• The Fourier structure of low degree polynomials
• On the Structure of Quintic Polynomials
• Correlation Testing for Affine Invariant Properties on ${\mathbb{F}}_p^n$ in the High Error Regime