Deterministic Extractors for Independent-Symbol Sources

摘要: In this paper, we consider the task of deterministically extracting randomness from sources consisting a sequence n independent symbols {0,1}d. The only guarantee on such source is that whole has min-entropy k . We give an explicit deterministic extractor which extract Ω(logk-loglog(1/ e)) bits with error e , for any n, d, ∈ \BBN and (0,1). For larger min-entropy, can even more randomness. When ≥ n1/2+γ, constant γ (0,1/2), m=k-O(d log(1/ 2-Ω(nγ). logcn some c > 0, m=k-(1/ e)O(1) k-Ω(1). Our results generalize those Kamp Zuckerman Gabizon work bit-fixing (with d=1 each bit being either fixed or perfectly random). Moreover, show existence nonexplicit m=k-O(log(1/ whenever k=ω(d+log(n/ Finally, to sources, extractor, seeded not, must suffer entropy loss k-m=Ω(log(1/ e)). This generalizes lower bound Radhakrishnan Ta-Shma general sources.