Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2009 | public
Journal Article

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes

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 et al. [2007] 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 [2005]. 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, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1/poly(n)).

Additional Information

Copyright © 2009 ACM. RECEIVED JUNE 2008; REVISED JANUARY 2009; ACCEPTED MARCH 2009. Preliminary versions of this article appeared as Technical Report TR06-134 in Electronic Colloquium on Computational Complexity, 2006, and in Proceedings of the 22nd Annual IEEE Conference on Computional Complexity (CCC'07), pp. 96–108. V. Guruswami was supported by NSF grants CCF-0343672 and CCF-0835814, a Sloan Research Fellowship, and a David and Lucile Packard Foundation Fellowship. C. Umans was supported by NSF CCF-0346991, NSF CCF-0830787, BSF 2004329, a Sloan Research Fellowship, and an Okawa Foundation research grant. S. Vadhan was supported by NSF CCF-0133096, ONR N00014-04-1-0478, BSF 2002246, a Guggenheim Fellowship, and the Miller Institute for Basic Research in Science. This article began with a conversation at the BIRS workshop "Recent Advances in Computation Complexity" in August 2006. We thank the organizers for inviting us, and BIRS for hosting the workshop. We also thank Kai-Min Chung, Ariel Gabizon, Oded Goldreich, Prahladh Harsha, Farzad Parvaresh, Jaikumar Radhakrishnan, Omer Reingold, Ronen Shaltiel, Prasad Tetali, Dieter van Melkebeek, Michael von Korff, and the anonymous CCC and JACM reviewers for helpful comments. We thank Ariel Gabizon for an important observation that enabled the construction in Section 7.2. E.4 [Coding and Information Theory]: error control codes; F.0 [Theory of Computation]: General; G.2.2 [Discrete Mathematics]: Graph Theory; G.3 [Probability and Statistics]: random number generation

Additional details

Created:
August 21, 2023
Modified:
October 18, 2023