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.