Paper Info
Title
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: 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 [36], worked only when both sources had entropy rate 1-delta. 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: We introduce the class of any-order-small-space sources, generalizing the class of small-space sources studied by Kamp et al. [22]. 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. 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, log p. Previously this was known only for a tiny constant instead of .24, for p = 2 [36]. 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.
Year
DOI
Venue
2016
10.4230/LIPIcs.CCC.2016.7
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
extractors,derandomization,explicit construction
Conference
50
ISSN
Citations 
PageRank 
1868-8969
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Eshan Chattopadhyay18411.71
David Zucherman22588266.65