Published: May 27, 2009

**Keywords:**pseudorandom, explicit construction, polynomial, low degree

**Categories:**short, complexity theory, pseudorandom generators, explicit construction, polynomials, low degree, degree-d norm, Gowers norm, Fourier analysis

**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.