Harvard Theory of Computation Seminar
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
Salil Vadhan, Harvard.
Place and Time: Monday, February 5, Maxwell Dworkin 221
Refreshments at 2:30pm, talk at 2:45pm
ABSTRACT
We give an improved explicit construction of highly
unbalanced bipartite expander graphs with expansion arbitrarily
close to the degree (which is polylogarithmic in the number of
vertices). Both the degree and the number of right-hand vertices
are polynomially close to optimal, whereas the previous
constructions of Ta-Shma, Umans, and Zuckerman (STOC `01) required
at least one of these to be quasipolynomial in the optimal. Our
expanders have a short and self-contained description and analysis,
based on the ideas underlying the recent list-decodable
error-correcting codes of Parvaresh and Vardy (FOCS `05).
Our expanders can be interpreted as near-optimal "randomness
condensers," reducing 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 is optimal up to constant factors, while
being much simpler than the previous construction of Lu et al. (STOC
`03) and improving upon it when the error parameter is small (e.g.
1/poly(n)).
Joint work with Venkatesan Guruswami and Christopher Umans.