Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-075 | 9th August 2007 00:00

Unconditional pseudorandom generators for low degree polynomials

RSS-Feed




TR07-075
Authors: Shachar Lovett
Publication: 10th August 2007 08:38
Downloads: 3418
Keywords: 


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.



ISSN 1433-8092 | Imprint