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 ε^2O(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 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.