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.

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

The case ${\displaystyle d=1}${\displaystyle d=1} 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 ${\displaystyle \ell =\log n+O(\log(\epsilon ^{-1}))}${\displaystyle \ell =\log n+O(\log(\epsilon ^{-1}))}, 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 ${\displaystyle 2^{d}}${\displaystyle 2^{d}} small-bias spaces fools polynomials of degree ${\displaystyle d}${\displaystyle d}. Viola (2008) proves that, in fact, taking the sum of only ${\displaystyle d}${\displaystyle d} small-bias generators is sufficient to fool polynomials of degree ${\displaystyle d}${\displaystyle d}. The analysis of Viola (2008) gives a seed length of ${\displaystyle \ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))}${\displaystyle \ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))}.

• Bogdanov, Andrej; Viola, Emanuele (2007). "Spectral Graph Theory and its Applications". 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). pp. 41–51. doi:10.1109/FOCS.2007.56. ISBN 978-0-7695-3010-9. S2CID 1142549.
• Lovett, Shachar (2009), "Unconditional Pseudorandom Generators for Low Degree Polynomials", Theory of Computing, 5 (3): 69–82, doi:10.4086/toc.2009.v005a003
• Naor, Joseph; Naor, Moni (1990), "Small-bias probability spaces: Efficient constructions and applications", Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90, pp. 213–223, CiteSeerX 10.1.1.421.2784 , doi:10.1145/100216.100244, ISBN 978-0897913614, S2CID 14031194
• Viola, Emanuele (2008). "The Sum of d Small-Bias Generators Fools Polynomials of Degree D". 2008 23rd Annual IEEE Conference on Computational Complexity (PDF). pp. 124–127. CiteSeerX 10.1.1.220.1554 . doi:10.1109/CCC.2008.16. ISBN 978-0-7695-3169-4.

• Pseudorandomness

• Articles with short description
• Short description matches Wikidata