ECCC-Report TR13-025https://eccc.weizmann.ac.il/report/2013/025Comments and Revisions published for TR13-025en-usMon, 08 Apr 2013 19:09:31 +0300
Revision 1
| Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy |
Xin Li
https://eccc.weizmann.ac.il/report/2013/025#revision1We 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.Mon, 08 Apr 2013 19:09:31 +0300https://eccc.weizmann.ac.il/report/2013/025#revision1
Paper TR13-025
| Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy |
Xin Li
https://eccc.weizmann.ac.il/report/2013/025We 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.Fri, 08 Feb 2013 13:53:51 +0200https://eccc.weizmann.ac.il/report/2013/025