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

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.