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.

Corrected some minor mistakes and references

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.