Tuesday, April 19th, 2011
4:00pm - 5:15pm, in TBD -

Salil Vadhan

Harvard University

The Unified Theory of Pseudorandomness

Abstract: Pseudorandomness is the theory of efficiently generating objects that ``look random'' despite being constructed with little or no randomness. One of the achievements of this research area has been the realization that a number of fundamental and widely studied `pseudorando'' objects are all almost equivalent when viewed appropriately. These objects include pseudorandom generators, expander graphs, list-decodable errorcorrecting codes, averaging samplers, and hardness amplifiers. In this survey, we describe the connections between all of these objects, showing how they can all be cast within a single ``list-decoding framework'' that brings out both their similarities and differences.