In theoretical computer science, a pseudorandom generator for low-degree polynomials is an efficient procedure that maps a short truly random seed to a longer pseudorandom string in such a way that low-degree polynomials cannot distinguish the output distribution of the generator from the truly random distribution. That is, evaluating any low-degree polynomial at a point determined by the pseudorandom string is statistically close to evaluating the same polynomial at a point that is chosen uniformly at random.
Pseudorandom generators for low-degree polynomials are a particular instance of pseudorandom generators for statistical tests, where the statistical tests considered are evaluations of low-degree polynomials.
A pseudorandom generator
G:F\ell → Fn
d
F
\ell
n
n
F
d
G
p(x1,...,xn)
p(Un)
p(G(U\ell))
\epsilon
Uk
Fk
The case
d=1
\ell=logn+O(log(\epsilon-1))
conjectured that the sum of small-bias generators fools low-degree polynomials and were able to prove this under the Gowers inverse conjecture. proved unconditionally that the sum of
2d
d
d
d
\ell=d ⋅ logn+O(2d ⋅ log(\epsilon-1))