דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Unconditional pseudorandom generators for low degree
event speaker icon
שחר לווט
event date icon
יום ראשון, 25.11.2007, 10:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.
[בחזרה לאינדקס האירועים]