Pseudorandom generators for polynomials

In theoretical computer science a pseudorandom generator for low-degree polynomials is an efficiently computable function whose output is indistinguishable from the uniform distribution by evaluation of low-degree polynomials in the following sense.

Definition

A pseudorandom generator $G: \mathbb{F}^s \rightarrow \mathbb{F}^n$ for polynomials of degree d over a Finite field F is an efficient procedure that stretches s < < n field elements into n field elements and fools any polynomial of degree d in n variables over F: For every such polynomial p, the statistical distance between the distributions p(U_n), for uniform U_n in $\mathbb{F}^n$, and p(G(U_s)), for uniform U_s in $\mathbb{F}^s$, is at most a small $\epsilon$.

Construction

The case of linear polynomials is solved by small-bias spaces which give constructions with seed length $s = O(\log n + \log (1/\epsilon))$ (this is optimal up to constant factors). Following the sequence of papers ([1], [2]) it was established in [3] that a sum of d small-bias spaces fools degree d polynomials. This gives a construction with seed length $s = O(\log n + 2^d \log(1/\epsilon))$.

References

• [4] (The paper proposed taking a sum of independent small-bias spaces for fooling low-degree polynomials).
• [5] (The paper gave the first unconditional result showing that sum of 2^d small-bias spaces fools low-degree polynomials).
• [6] (The paper shows that sum of d small-bias spaces fools low-degree polynomials).