Girish Mahajan (Editor)

Pseudorandom generators for polynomials

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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 : F ℓ → F n for polynomials of degree d over a finite field F is an efficient procedure that maps a sequence of ℓ field elements to a sequence of n field elements such that any n -variate polynomial over F of degree d is fooled by the output distribution of G . In other words, for every such polynomial p ( x 1 , … , x n ) , the statistical distance between the distributions p ( U n ) and p ( G ( U ℓ ) ) is at most a small ϵ , where U k is the uniform distribution over F k .

Construction

The case 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 ℓ = log ⁡ n + O ( log ⁡ ( ϵ − 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 2 d small-bias spaces fools polynomials of degree d . Viola (2008) proves that, in fact, taking the sum of only d small-bias generators is sufficient to fool polynomials of degree d . The analysis of Viola (2008) gives a seed length of ℓ = d ⋅ log ⁡ n + O ( 2 d ⋅ log ⁡ ( ϵ − 1 ) ) .

References

Pseudorandom generators for polynomials Wikipedia
(Text) CC BY-SA