CS Colloquia: Expanders and Extractors from Parvaresh-Vardy Codes

Title: Expanders and Extractors from Parvaresh-Vardy CodesSpeaker: Prof. Chris Umans(CALTECH)ABSTRACT:
Expanders and extractors are fundamental combinatorial objects with
a wide variety of applications in theoretical computer science.In this work we give the best-to-date explicit construction of highly
unbalanced bipartite expander graphs with expansion arbitrarily
close to the degree. 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,'' that 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 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.Joint work with Venkat Guruswami and Salil Vadhan.BIO:
Chris Umans received his Ph.D. in Computer Science from Berkeley in 2000.
After spending two years as a postdoc in the Theory Group at Microsoft
Research, he joined the Computer Science faculty at Caltech in 2002. His
research interests are in theoretical computer science, especially complexity
theory. He is the recipient of an NSF CAREER award, an Alfred P. Sloan
Research Fellowship, and two CCC Best Paper Awards.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia