Title: Pseudorandom generators for low degree polynomials
Speaker: Andrej Bogdanov, University of California, Berkeley
Date: November 1, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Algorithmic derandomization studies whether the output of randomized computations is affected when the random source is replaced with a pseudorandom source that uses much less randomness. For a fixed class of computations, the amount of randomness that must be used by the pseudorandom source can be lower bounded by a counting argument. A pseudorandom source is considered "optimal" if the amount of randomness it uses matches this lower bound.
There are only few classes of computations for which efficient constructions of close to optimal pseudorandom sources are known. I will present a construction of such sources for the class of computations described by low-degree polynomials over a sufficiently large field.