LIPIcs.CCC.2016.7.pdf
- Filesize: 0.63 MB
- 28 pages
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. 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} -> {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 by Raz and Yehudayoff. 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.
Feedback for Dagstuhl Publishing