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.

corrected some references; added subsequent work

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.