Show simple item record

dc.contributor.authorKamp, Jesse
dc.contributor.authorRao, Anup
dc.contributor.authorVadhan, Salil P.
dc.contributor.authorZuckerman, David
dc.date.accessioned2014-08-19T20:32:51Z
dc.date.issued2011
dc.identifier.citationKamp, Jesse, Anup Rao, Salil Vadhan, and David Zuckerman. 2011. Deterministic Extractors for Small-Space Sources. Journal of Computer and System Sciences 77, no. 1: 191–220.en_US
dc.identifier.issn0022-0000en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:12724035
dc.description.abstractWe give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on n{0,1} as sources generated by width s2 branching programs. Specifically, there is a constant η>0 such that for any ζ>n−η, our algorithm extracts m=(δ−ζ)n bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where s=Ω(ζ3n). Previously, nothing was known for δ≤1/2, even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of r independent smaller sources over ℓ{0,1}, where the total min-entropy over all the smaller sources is k. We give deterministic extractors for such sources when k is as small as polylog(r), for small enough ℓ.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherElsevier BVen_US
dc.relation.isversionofdoi:10.1016/j.jcss.2010.06.014en_US
dc.relation.hasversionhttps://homes.cs.washington.edu/~anuprao/pubs/small-space.pdfen_US
dash.licenseLAA
dc.subjectRandomness extractorsen_US
dc.subjectPseudorandomnessen_US
dc.subjectMarkov chainsen_US
dc.subjectSamplable sourcesen_US
dc.subjectBit-fixing sourcesen_US
dc.subjectIndependent sourcesen_US
dc.titleDeterministic Extractors for Small-Space Sourcesen_US
dc.typeJournal Articleen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalJournal of Computer and System Sciencesen_US
dash.depositing.authorVadhan, Salil P.
dash.waiver2010-01-07
dc.date.available2014-08-19T20:32:51Z
dc.identifier.doi10.1016/j.jcss.2010.06.014*
workflow.legacycommentsFrom Waiver Tableen_US
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record