Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes

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

Full description

Saved in:
Bibliographic Details
Main Authors: Guruswami, V., Umans, C., Vadhan, S.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Bipartite graph
Computational complexity
Computer science
condensers
Data structures
Decoding
Error correction codes
error-correcting codes
expander graphs
Graph theory
list decoding
Polynomials
Random number generation
randomness extractors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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," 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 (e.g. 1/poly(n)).
ISSN:1093-0159
2575-8403
DOI:10.1109/CCC.2007.38