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 TR15-151 | 9th April 2016 17:31

New Extractors for Interleaved Sources

RSS-Feed




Revision #1
Authors: Eshan Chattopadhyay, David Zuckerman
Accepted on: 9th April 2016 17:31
Downloads: 205
Keywords: 


Abstract:

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,
explicit extractors for $2$-interleaved sources on $\{ 0,1\}^{2n}$ when one source has min-entropy at least $ (1-\delta)n$ and the other
has min-entropy at least $c\log n$.
The best previous construction, by Raz and Yehudayoff, worked only when both sources had entropy rate $1-\delta$.

(2) For some $c>0$ and any large enough prime $p$, explicit extractors for $2$-interleaved sources on $[p]^{2n}$ when one source has min-entropy rate at least .51
and the other source has min-entropy rate at least $(c\log n)/n$.

(3) We use these to obtain the following applications:

(a) We introduce the class of any-order-small-space sources, generalizing the class of small-space sources studied by Kamp et al. We construct extractors for such sources with min-entropy rate close to $1/2$. Using the Raz-Yehudayoff construction would require
entropy rate close to 1.

(b) For any large enough prime $p$, we exhibit an explicit function $f:[p]^{2n} \rightarrow \{ 0,1\} $ such that the randomized best-partition communication complexity of $f$ with error $1/2-2^{-\Omega(n)}$ is at least $.24 n \log p$. Previously this was known only for a tiny constant instead of $.24$, for $p=2$ by Raz-Yehudayoff.

(c) We introduce non-malleable extractors in the interleaved model.
For any large enough prime $p$, we give an explicit construction of a weak-seeded non-malleable extractor for sources over $[p]^n$ with min-entropy rate .51. Nothing was known previously, even for almost full min-entropy.



Changes to previous version:

corrected some references; added subsequent work


Paper:

TR15-151 | 14th September 2015 23:55

New Extractors for Interleaved Sources


Abstract:

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,
explicit extractors for $2$-interleaved sources on $\{ 0,1\}^{2n}$ when one source has min-entropy at least $ (1-\delta)n$ and the other
has min-entropy at least $c\log n$.
The best previous construction, by Raz and Yehudayoff, worked only when both sources had entropy rate $1-\delta$.

(2) For some $c>0$ and any large enough prime $p$, explicit extractors for $2$-interleaved sources on $[p]^{2n}$ when one source has min-entropy rate at least .51
and the other source has min-entropy rate at least $(c\log n)/n$.

(3) We use these to obtain the following applications:

(a) We introduce the class of any-order-small-space sources, generalizing the class of small-space sources studied by Kamp et al. We construct extractors for such sources with min-entropy rate close to $1/2$. Using the Raz-Yehudayoff construction would require
entropy rate close to 1.

(b) For any large enough prime $p$, we exhibit an explicit function $f:[p]^{2n} \rightarrow \{ 0,1\} $ such that the randomized best-partition communication complexity of $f$ with error $1/2-2^{-\Omega(n)}$ is at least $.24 n \log p$. Previously this was known only for a tiny constant instead of $.24$, for $p=2$ by Raz-Yehudayoff.

(c) We introduce non-malleable extractors in the interleaved model.
For any large enough prime $p$, we give an explicit construction of a weak-seeded non-malleable extractor for sources over $[p]^n$ with min-entropy rate .51. Nothing was known previously, even for almost full min-entropy.



ISSN 1433-8092 | Imprint