Show simple item record

dc.contributor.authorGuruswami, Venkatesan
dc.contributor.authorUmans, Christopher
dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2015-03-11T17:22:03Z
dc.date.issued2009
dc.identifier.citationGuruswami, Venkatesan, Christopher Umans, and Salil Vadhan. 2009. “Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.” Journal of the ACM 56, 4: 1–34.en_US
dc.identifier.issn0004-5411en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:14117746
dc.description.abstractWe 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)).en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherAssociation for Computing Machinery (ACM)en_US
dc.relation.isversionofdoi:10.1145/1538902.1538904en_US
dash.licenseLAA
dc.subjectexpander graphsen_US
dc.subjectrandomness extractorsen_US
dc.subjecterror-correcting codesen_US
dc.subjectlist decodingen_US
dc.subjectcondensersen_US
dc.titleUnbalanced expanders and randomness extractors from Parvaresh-Vardy codesen_US
dc.typeJournal Articleen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalJournal of the ACMen_US
dash.depositing.authorVadhan, Salil P.
dash.waiver2009-05-07
dc.date.available2015-03-11T17:22:03Z
dc.identifier.doi10.1145/1538902.1538904*
workflow.legacycommentsFAR 2010. Can post manuscript per sherpa.en_US
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record