Pseudorandom generators for polynomials

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.

over a finite field

is an efficient procedure that maps a sequence of

field elements to a sequence of

field elements such that any

is fooled by the output distribution of

, the statistical distance between the distributions

corresponds to pseudorandom generators for linear functions and is solved by small-bias generators.

For example, the construction of Naor & Naor (1990) achieves a seed length of

ℓ = log ⁡ n +

, which is optimal up to constant factors.

Bogdanov & Viola (2007) conjectured that the sum of small-bias generators fools low-degree polynomials and were able to prove this under the Gowers inverse conjecture.

Lovett (2009) proved unconditionally that the sum of

small-bias spaces fools polynomials of degree

Viola (2008) proves that, in fact, taking the sum of only

small-bias generators is sufficient to fool polynomials of degree

The analysis of Viola (2008) gives a seed length of

ℓ = d ⋅ log ⁡ n +