Title: Lossless Expanders and Randomness Extractors from Parvaresh-Vardy Codes
Speaker: Venkatesan Guruswami, University of Washington
Date: Wednesday, February 21, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We give a new construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Our expanders have a short and self-contained description and analysis, based on the algebraic ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS `05).
Our expanders can be interpreted as "randomness condensers" that achieve near-optimal compression of a weak random source while preserving all of its entropy. This reduces the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new construction of randomness extractors that extract 99.9% of the source entropy using a logarithmic (up to constant factors) length seed. Our construction is much simpler than the previous construction of Lu et al. (STOC `03) that achieved a similar result, and in addition improves upon it when the error parameter is small (e.g. 1/poly(n)).
Joint work with Christopher Umans and Salil Vadhan.