CSAIL Event Calendar: Previous Series

Expander Graphs, Randomness Extractors, and List-Decodable Codes

Speaker: Salil Vadhan , Harvard University
Date: March 20 2007
Time: 4:15PM to 5:30PM
Location: 32-G449 (Patil/Kiva)
Host: Madhu Sudan, MIT

One of the exciting developments in the theory of pseudorandomness has been the realization that a number of fundamental and widely studied objects are almost equivalent when interpreted appropriately. These objects include expander graphs, randomness extractors, list-decodable error-correcting codes, pseudorandom generators, and randomness-efficient samplers.

In this talk, we will illustrate some of these connections and their power by showing how recent breakthrough constructions of list-decodable codes, due to Parvaresh and Vardy (FOCS `05) and Guruswami and Rudra (STOC `06), can be used to give much simpler and improved constructions of both randomness extractors and highly unbalanced bipartite expander graphs.

Joint work with Venkatesan Guruswami and Christopher Umans.

See other events that are part of Theory Colloquium Spring 2007

See other events happening in March 2007