### DIMACS Theoretical Computer Science Seminar

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.