Theory of Computing
-------------------
Title     : Unconditional Pseudorandom Generators for Low-Degree Polynomials
Authors   : Shachar Lovett
Volume    : 5
Number    : 3
Pages     : 69-82
URL       : https://theoryofcomputing.org/articles/v005a003

Abstract
--------

We give an explicit construction of pseudorandom generators against 
low-degree polynomials over finite fields.   Pseudorandom generators
against linear polynomials, known as "small-bias generators," were 
first introduced by Naor and Naor (STOC' 1990).  We show that the sum 
of  2^d  independent small-bias generators with error epsilon^{2^{O(d)}}
is a pseudorandom generator against degree  d  polynomials with error
epsilon. This gives a generator with seed length  2^{O(d)} log(n/epsilon). 
Our construction follows the breakthrough result of Bogdanov and Viola 
(FOCS 2007). Their work shows that the sum of $d$ small-bias generators is 
a pseudo-random generator against degree $d$ polynomials, assuming the
Inverse Conjecture for the Gowers Norm. However, this conjecture is only 
proven for  d=2,3,  and was later shown to be false for  d >= 4 
by Green and Tao (2008) and independently by the author, Roy Meshulam,
and Alex Samorodnitsky (STOC 2008). The main advantage of our work is that 
it does not rely on any unproven conjectures.