Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-025 | 8th April 2013 19:09

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

RSS-Feed




Revision #1
Authors: Xin Li
Accepted on: 8th April 2013 19:09
Downloads: 981
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


Paper:

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: 1523
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.



ISSN 1433-8092 | Imprint