Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-072 | 11th August 2008 00:00

Worst case to Average case reductions for polynomials


Authors: Shachar Lovett, Tali Kaufman
Publication: 11th August 2008 17:37
Downloads: 1283


A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower degree polynomials. Green and Tao [GT07] have shown that over large fields (i.e when d < |\F|) a biased polynomial must have low rank. They have also conjectured that bias implies low rank over general fields, but their proof technique fails to show that. 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 approximated by a few polynomials of bounded degree (i.e. a polynomial with non negligible correlation with a function of few bounded degree polynomials), can be computed by a few polynomials of bounded degree. We derive some relations between our results to the construction of pseudorandom generators. Our work provides another evidence to the structure vs. randomness dichotomy.

ISSN 1433-8092 | Imprint