Deterministic Extractors for Independent-Symbol Sources
Chia-Jung Lee, Chi-Jen Lu, Shi‐Chun Tsai · IEEE Transactions on Information Theory · 2010
In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence ofnindependent symbols from {0,1}d. The only randomness guarantee on such a source is that the whole source has min-entropyk. We give an explicit deterministic extractor which extract Ω(logk-loglog(1/ ε)) bits with error ε , for anyn,d,k∈ \BBN and ε ∈ (0,1). For sources with a larger min-entropy, we can extract even more randomness. Whenk≥n1/2+γ, for any constant γ ∈ (0,1/2), we can extractm=k-O(dlog(1/ ε)) bits with any error ε ≥ 2-Ω(nγ). Whenk≥ logcn, for some constantc> 0, we can extractm=k-(1/ ε)O(1) bits with any error ε ≥k-Ω(1). Our results generalize those of Kamp and Zuckerman and Gabizon which only work for bit-fixing sources (withd=1 and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a nonexplicit deterministic extractor which can extractm=k-O(log(1/ ε)) bits wheneverk=ω(d+log(n/ ε)) . Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy lossk-m=Ω(log(1/ ε)). This generalizes a lower bound of Radhakrishnan and Ta-Shma on extracting from general sources.