Worst Case to Average Case Reductions for Polynomials
| dc.creator | Kaufman, Tali | |
| dc.creator | Lovett, Shachar | |
| dc.date | 2008-06-27 | |
| dc.date | 2008-07-02 | |
| dc.date.accessioned | 2026-07-07T09:47:50Z | |
| dc.date.available | 2026-07-07T09:47:50Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0806.4535 | |
| dc.identifier | http://arxiv.org/abs/0806.4535 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163993 | |
| dc.subject | Combinatorics | |
| dc.title | Worst Case to Average Case Reductions for Polynomials | |
| dc.type | text |