Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Unconditional pseudorandom generators for low degree
event speaker icon
Shachar Lovett
event date icon
Sunday, 25.11.2007, 10:30
event location icon
Room 337-8 Taub Bld.
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 \cite{BV}. 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.