Volume 5 (2009) Article 3 pp. 69-82

Unconditional Pseudorandom Generators for Low-Degree Polynomials

by Shachar Lovett

Received: July 14, 2008
Published: May 27, 2009

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$ 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)}$ against degree-$d$ polynomails. 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 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 \ge 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.

DOI: 10.4086/toc.2009.v005a003

© 2009 Shachar Lovett
Licensed under a Creative Commons Attribution License (CC-BY)