Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
By Venkatesan Guruswami, C. Umans, Salil P. Vadhan. Cybersecurity and Cyberforensics Conference, 2007
467 citations recorded by the source corpus.
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)).
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/06521fd89f6233bd779b7754a4042dad3008e650
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Computer Networks and Communications
Citations in the corpus
- Sparse Recovery Using Sparse Matrices (2010, unknown): “However, it is known [23] how to explicitly construct expanders with left degree d 1⁄4 Oððlog jUjÞðlog sÞ= Þ1þ1= and right set size ðd2s1þ Þ, for any fixed > 0.”
- Optimal fractional repetition codes and fractional repetition batch codes (2015, background): “Hence, to have an FR code with file size M(k), one need to construct a (k, M(k) k ) expander graph, where M(k) k is its expansion factor [5].”