Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy
Xin Li · 2013
We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on n bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as log n+O(1). However, even to extract from a constant number of independent sources, previously the best known extractors require the min-entropy to be at least nδfor any constant δ > 0 [1], [2], [3]. For sources on n bits with min-entropy k ≥ polylog(n), previously the best known extractor needs to use O(log(log n/log k))+O(1) independent sources Li12d. In this paper, we construct the first explicit extractor for a constant number of independent sources on n bits with min-entropy k ≥ polylog(n). Thus, for the first time we get extractors for independent sources that are close to optimal. Our extractor is obtained by improving the condenser for structured somewhere random sources in [3], which is based on a connection between the problem of condensing somewhere random sources and the problem of leader election in distributed computing.