Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

摘要

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 Rao06, BarakRSW06, Li12d. For sources on n bits with min-entropy k ≥ q 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 ≥ q 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 Li12d, which is based on a connection between the problem of condensing somewhere random sources and the problem of leader election in distributed computing.