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.