Worst Case to Average Case Reductions for Polynomials

Tali Kaufman, Shachar Lovett

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.…