標題: Deterministic Extractors for Independent-Symbol Sources
作者: Lee, Chia-Jung
Lu, Chi-Jen
Tsai, Shi-Chun
資訊工程學系
Department of Computer Science
關鍵字: Independent-symbol sources;min-entropy;pseudo-randomness;randomness extractors
公開日期: 1-Dec-2010
摘要: In 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 extract Omega(log k - log log(1/epsilon)) bits with error epsilon, for any, n, d, k is an element of N and epsilon is an element of (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 (1, 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 - (1/epsilon)(O(1)) bits with any error epsilon >= k(-Omega(1)). Our results generalize those of Kamp and Zuckerman and Gabizon et al. which only work for bit-fixing sources (with d = 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 extract m = k - O(log(1/epsilon)) bits whenever k = omega(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 = Omega(log(1/epsilon)). This generalizes a lower bound of Radhakrishnan and Ta-Shma on extracting from general sources.
URI: http://dx.doi.org/10.1109/TIT.2010.2079012
http://hdl.handle.net/11536/26303
ISSN: 0018-9448
DOI: 10.1109/TIT.2010.2079012
期刊: IEEE TRANSACTIONS ON INFORMATION THEORY
Volume: 56
Issue: 12
起始頁: 6501
結束頁: 6512
Appears in Collections:Articles


Files in This Item:

  1. 000284419900042.pdf