pdf icon
Volume 5 (2009) Article 3 pp. 69-82
Unconditional Pseudorandom Generators for Low Degree Polynomials
Received: July 14, 2008
Published: May 27, 2009
Download article from ToC site:
[PDF (234K)]    [PS (715K)]    [PS.GZ (203K)]
[Source ZIP]
Keywords: pseudorandom, explicit construction, polynomial, low degree
ACM Classification: F.2.1, F.1.3, F.2.2, G.2, G.3
AMS Classification: 68Q10, 68Q17, 12Y05, 60C05

Abstract: [Plain Text Version]

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.