Unconditional pseudorandom generators for low degree polynomials

We give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. We show that the sum of 2 d small-biased generators with error ε 2 O(d) is a pseudorandom generator against degree d polynomials with error ε. This gives a generator with seed length 2 O(d) log(n/ε). Our construction follows the recent breakthrough result of Bogadnov and Viola. Their work shows that the sum of d small-biased generators is a pseudo-random generator against degree d polynomials, assuming the Inverse Gowers Conjecture. However, this conjecture is only proven for d=2,3. The main advantage of our work is that it does not rely on any unproven conjectures.

Authors

• Shachar Lovett

Keywords

• low degree tests
• fourier analysis
• pseudorandom generators