IME: 1:30-2:20 pm, March 27, 2007 PLACE: CSE 403 SPEAKER: Venkat Guruswami University of Washington TITLE: Lossless Expanders and Extractors from Parvaresh-Vardy Codes 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 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. We also show, using ideas from the work of Guruswami and Rudra (STOC'06), that a natural construction based on Reed-Solomon codes yields a condenser that retains a (1 - delta) fraction of the source min-entropy, for any desired constant delta > 0. Our results reduce 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 Chris Umans (Caltech) and Salil Vadhan (Harvard).