Haifa University - Dept. of CS Theory Seminar Speaker : Shachar Lovett, Weizmann. Title: "Unconditional pseudorandom generators for low degree polynomials" Date: Thursday, Jan. 10. Place: Haifa U. Education Building, room 570. Time: 12:15 - 13:30 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 \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.