ECCC-Report TR12-147https://eccc.weizmann.ac.il/report/2012/147Comments and Revisions published for TR12-147en-usWed, 07 Nov 2012 16:13:27 +0200
Paper TR12-147
| New Independent Source Extractors with Exponential Improvement |
Xin Li
https://eccc.weizmann.ac.il/report/2012/147We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only uses $O(\log(\frac{\log n}{\log k}))+O(1)$ independent sources. Thus, our result improves the previous best result exponentially. We then use our new extractor to give improved network extractor protocols, as defined in \cite{KalaiLRZ08}. The network extractor protocols also give new results in distributed computing with general weak random sources which dramatically improve previous results. For example, we can tolerate a nearly optimal fraction of faulty players in synchronous Byzantine agreement and leader election, even if the players only have access to independent $n$-bit weak random sources with min-entropy as small as $k=polylog(n)$.
Our extractor for independent sources is based on a new condenser for somewhere random sources with a special structure. We believe our techniques are interesting in their own right and are promising for further improvement.Wed, 07 Nov 2012 16:13:27 +0200https://eccc.weizmann.ac.il/report/2012/147