__
TR07-075 | 9th August 2007 00:00
__

#### Unconditional pseudorandom generators for low degree polynomials

**Abstract:**
We give an explicit construction of pseudorandom

generators against low degree polynomials over finite fields. We

show that the sum of $2^d$ small-biased 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)}$. Our construction follows the

recent breakthrough result of Bogadnov and Viola. Their

work shows that the sum of $d$ small-biased generators is a

pseudo-random generator against degree $d$ polynomials, assuming the

Inverse Gowers Conjecture. However, this conjecture is only proven

for $d=2,3$. The main advantage of our work is that it

does not rely on any unproven conjectures.