Unconditional pseudorandom generators for low degree polynomials

We give an explicit construction of a pseudorandom,generator 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)log(n/e) against degree-d polynomails. Our construction follows the break- through 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, assum- ing a conjecture in additive combinatorics, known as the inverse conjecture for the Gowers norm. However, this conjecture was proven only for d = 2,3. The main advantage of this work is that it does not rely on any unproven conjectures. Subsequently, the inverse conjecture for the Gowers norm was shown to be false for d 4 by Green and Tao (2008) and independently by the author, Roy Meshulam, and Alex Samorodnitsky (STOC 2008). A revised version of the conjecture was proved by Bergelson, Tao, and Ziegler (2009). Additionally, Viola (CCC 2008) showed the original construction of Bogdanov and Viola to hold unconditionally. ACM Classification: F.2.1, F.1.3, F.2.2, G.2, G.3