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

by Xin Li

Oded's comments

This work greatly improves the amount of min-entropy that is required for efficient randomness extraction from a constant number of weak random sources: Rather than min-entropy that is a constant power of the length, it allows min-entropy that is polylogarithmic in the length.

Remarkablly, especially given the complexity of the ideas involved, the overview provided in Section 1 and 2.1 is very clear and accessible also to readers who are not experts in the area. (Indeed, Section 2.2 is harder to follow, especially to readers not familiar with work on non-malleable condensers, but even here a commendable effort is made by the author and the reader may be able to get some ideas (especially from the first page of Sec 2.2).) In addition, Table 1 (on page 3) provides a useful summary of the known and new results.

Add'l comments (based on presentation by Gil Cohen [Feb'14]): The starting point is Anup Rao's idea of using a seeded extractor in order to map one source into a list of (polynomailly many) strings such that most of them are almost random but quite dependent. Using an additional source (and employing ideas from ``alternating extraction'' [Dodis and Wichs]), this list is converted into a list of shorter (by factor of $h$) strings that are almost $h$-wise independent. Using yet another source (and employing Uri Feige's ``smallest committee'' idea [FOCS'99]), the size of the list is shrinked to polylogarithmic, and at this point known results (which require an additional constant number of cources) take over.

The original abstract

See ECCC TR13-025.

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^{\delta}$ for any constant $\delta > 0$ \cite{Rao06, BRSW06, Li13}. For sources on $n$ bits with min-entropy $k$, previously the best known extractor needs to use $O(\log(\log n/\log k))+O(1)$ independent sources \cite{Li13}.

In this paper, we construct the first explicit extractor for a constant number of independent sources on $n$ bits with polylogarithmic min-entropy. 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 \cite{Li13}, which is based on a connection between the problem of condensing somewhere random sources and the problem of leader election in distributed computing.


Back to list of Oded's choices.