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].
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2009
- Source ID
- 10.1145/1538902.1538904
Entities
People
- Christopher Umans
- Salil Vadhan
- Venkatesan Guruswami
Organizations
- Bulgarian Science Fund
- California Institute of Technology
- Carnegie Mellon University
- Division of Computing and Communication Foundations
- Harvard University
- Office of Naval Research