Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-147 | 7th November 2012 07:38

New Independent Source Extractors with Exponential Improvement


Authors: Xin Li
Publication: 7th November 2012 16:13
Downloads: 1366


We 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.

ISSN 1433-8092 | Imprint