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).