Expander Graphs, Randomness Extractors, and List-Decodable Codes
Speaker: Salil Vadhan , Harvard UniversityContact:
Date: March 20 2007
Time: 4:15PM to 5:30PM
Location: 32-G449 (Patil/Kiva)
Host: Madhu Sudan, MIT
Alexandr Andoni, email@example.comRelevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html
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