ECCC-Report TR08-072https://eccc.weizmann.ac.il/report/2008/072Comments and Revisions published for TR08-072en-usMon, 11 Aug 2008 17:37:13 +0300
Paper TR08-072
| Worst case to Average case reductions for polynomials |
Shachar Lovett,
Tali Kaufman
https://eccc.weizmann.ac.il/report/2008/072A 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.
Mon, 11 Aug 2008 17:37:13 +0300https://eccc.weizmann.ac.il/report/2008/072