__
Revision #1 to TR13-025 | 8th April 2013 19:09
__
#### Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revision #1
Authors:

Xin Li
Accepted on: 8th April 2013 19:09

Downloads: 1854

Keywords:

**Abstract:**
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.

**Changes to previous version:**
Corrected some minor mistakes and references

__
TR13-025 | 6th February 2013 09:32
__

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

TR13-025
Authors:

Xin Li
Publication: 8th February 2013 13:53

Downloads: 2475

Keywords:

**Abstract:**
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.