Worst Case to Average Case Reductions for Polynomials

Details Worst Case to Average Case Reductions for Polynomials Worst Case to Average Case Reductions for Polynomials

2008-06-27

arxiv.org/abs/0806.4535v2

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Worst Case to Average Case Reductions for Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Worst Case to Average Case Reductions for Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Worst Case to Average Case Reductions for Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-693054