Pseudorandom generators for polynomials

Template:Short description 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.

Definition

A pseudorandom generator $G:{𝔽}^{\ell }\to {𝔽}^n$ for polynomials of degree $d$ over a finite field $𝔽$ is an efficient procedure that maps a sequence of $\ell$ field elements to a sequence of $n$ field elements such that any $n$-variate polynomial over $𝔽$ of degree $d$ is fooled by the output distribution of $G$. In other words, for every such polynomial $p(x_1,\dots ,x_n)$, the statistical distance between the distributions $p(U_n)$ and $p(G(U_{\ell }))$ is at most a small $ϵ$, where $U_k$ is the uniform distribution over ${𝔽}^k$.

Construction

Lovett (3rd from left) in 2009

The case $d=1$ corresponds to pseudorandom generators for linear functions and is solved by small-bias generators. For example, the construction of Template:Harvtxt achieves a seed length of $\ell =\log n+O(\log ({ϵ}^{-1}))$, which is optimal up to constant factors.

Template:Harvtxt conjectured that the sum of small-bias generators fools low-degree polynomials and were able to prove this under the Gowers inverse conjecture. Template:Harvtxt proved unconditionally that the sum of $2^d$ small-bias spaces fools polynomials of degree $d$. Template:Harvtxt proves that, in fact, taking the sum of only $d$ small-bias generators is sufficient to fool polynomials of degree $d$. The analysis of Template:Harvtxt gives a seed length of $\ell =d\cdot \log n+O(2^d\cdot \log ({ϵ}^{-1}))$.

References

• Template:Cite book
• Template:Citation
• Template:Citation
• Template:Cite book