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.
Definition
A pseudorandom generator [math]\displaystyle{ G: \mathbb{F}^\ell \rightarrow \mathbb{F}^n }[/math] for polynomials of degree [math]\displaystyle{ d }[/math] over a finite field [math]\displaystyle{ \mathbb F }[/math] is an efficient procedure that maps a sequence of [math]\displaystyle{ \ell }[/math] field elements to a sequence of [math]\displaystyle{ n }[/math] field elements such that any [math]\displaystyle{ n }[/math]-variate polynomial over [math]\displaystyle{ \mathbb F }[/math] of degree [math]\displaystyle{ d }[/math] is fooled by the output distribution of [math]\displaystyle{ G }[/math]. In other words, for every such polynomial [math]\displaystyle{ p(x_1,\dots,x_n) }[/math], the statistical distance between the distributions [math]\displaystyle{ p(U_n) }[/math] and [math]\displaystyle{ p(G(U_\ell)) }[/math] is at most a small [math]\displaystyle{ \epsilon }[/math], where [math]\displaystyle{ U_k }[/math] is the uniform distribution over [math]\displaystyle{ \mathbb{F}^k }[/math].
Construction
The case [math]\displaystyle{ d=1 }[/math] corresponds to pseudorandom generators for linear functions and is solved by small-bias generators. For example, the construction of (Naor Naor) achieves a seed length of [math]\displaystyle{ \ell= \log n + O(\log (\epsilon^{-1})) }[/math], which is optimal up to constant factors.
(Bogdanov Viola) 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 [math]\displaystyle{ 2^d }[/math] small-bias spaces fools polynomials of degree [math]\displaystyle{ d }[/math]. (Viola 2008) proves that, in fact, taking the sum of only [math]\displaystyle{ d }[/math] small-bias generators is sufficient to fool polynomials of degree [math]\displaystyle{ d }[/math]. The analysis of (Viola 2008) gives a seed length of [math]\displaystyle{ \ell = d \cdot \log n + O(2^d \cdot \log(\epsilon^{-1})) }[/math].
References
- 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. http://eccc.hpi-web.de/report/2007/081/download.
- 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, doi:10.1145/100216.100244, ISBN 978-0897913614, http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias_abs.html
- Viola, Emanuele (2008). "The Sum of d Small-Bias Generators Fools Polynomials of Degree D". 2008 23rd Annual IEEE Conference on Computational Complexity. pp. 124–127. doi:10.1109/CCC.2008.16. ISBN 978-0-7695-3169-4. http://www.ccs.neu.edu/home/viola/papers/d.pdf.
 |  |
