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 can extract Ω(logk – logd loglog(1/e)) bits with error e, for any n,d,k∈ℕ and e∈(0,1). For larger min-entropy, even more randomness. When k≥n1/2+γ, constant γ∈(0,1/2), m=k–O(d log(1/e)) $\varepsilon \ge 2^{-\Omega(n^{\gamma})}$. k≥logcn, some c>0, m=k–d (1/e)O(1) e≥k−−Ω(1). Our results generalize those Kamp & Zuckerman Gabizon et al. work bit-fixing (with d=1 each bit being either fixed or perfectly random). Moreover, show existence non-explicit m=k–O(log(1/e)) whenever k=ω(d+log(n/e)). Finally, to sources, extractor, seeded not, must suffer entropy loss k–m = Ω(log(1/e)). This generalizes lower bound Radhakrishnan Ta-Shma respect general sources.