Full metadata record
DC FieldValueLanguage
dc.contributor.authorLee, Chia-Jungen_US
dc.contributor.authorLu, Chi-Jenen_US
dc.contributor.authorTsai, Shi-Chunen_US
dc.date.accessioned2014-12-08T15:17:49Z-
dc.date.available2014-12-08T15:17:49Z-
dc.date.issued2006en_US
dc.identifier.isbn3-540-35904-4en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/11536/12904-
dc.description.abstractIn this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence of n independent symbols from {0, 1}(d). The only randomness guarantee on such a source is that the whole source has min-entropy k. We give an explicit deterministic extractor which can extract Omega(log k-log d-log log(1/epsilon)) bits with error epsilon, for any n, d, k is an element of N and epsilon G (0, 1). For sources with a larger min-entropy, we can extract even more randomness. When k >= n(1/2+gamma) for any constant gamma is an element of (0, 1/2), we can extract m = k - O(d log(1/epsilon)) bits with any error epsilon >= 2(-Omega)(n(gamma)). When k >= log(c)n, for some constant c > 0, we can extract m = k - d(1/epsilon)(O(1)) bits with any error epsilon >= k(-Omega(1)). Our results generalize those of Kamp & Zuckerman and Gabizon et al. which only work for bit-fixing sources (with d = I and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a non-explicit deterministic extractor which can extract m = k-O(log(1/epsilon)) bits whenever k = w(d+log(n/epsilon)). Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy loss k-m = Q (log (1/epsilon)). This generalizes a lower bound of Radhakrishnan & Ta-Shma with respect to general sources.en_US
dc.language.isoen_USen_US
dc.titleDeterministic extractors for independent-symbol sourcesen_US
dc.typeArticle; Proceedings Paperen_US
dc.identifier.journalAUTOMATA, LANGUAGES AND PROGRAMMING, PT 1en_US
dc.citation.volume4051en_US
dc.citation.spage84en_US
dc.citation.epage95en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000239474500009-
Appears in Collections:Conferences Paper