Chattopadhyay, Eshan ;
Zuckerman, David
New Extractors for Interleaved Sources
Abstract
We study how to extract randomness from a Cinterleaved 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 2interleaved sources on {0,1}^{2n} when one source has minentropy at least (1delta)*n and the other has minentropy at least c*log(n). The best previous construction, by Raz and Yehudayoff, worked only when both sources had entropy rate 1delta.
(2) For some c>0 and any large enough prime p, explicit extractors for 2interleaved sources on [p]^{2n} when one source has minentropy rate at least .51 and the other source has minentropy rate at least (c*log(n))/n.
We use these to obtain the following applications:
(a) We introduce the class of anyordersmallspace sources, generalizing the class of smallspace sources studied by Kamp et al.. We construct extractors for such sources with minentropy rate close to 1/2. Using the RazYehudayoff 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 bestpartition communication complexity of f with error 1/22^{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 nonmalleable extractors in the interleaved model. For any large enough prime p, we give an explicit construction of a weakseeded nonmalleable extractor for sources over [p]^n with minentropy rate .51. Nothing was known previously, even for almost full minentropy.
BibTeX  Entry
@InProceedings{chattopadhyay_et_al:LIPIcs:2016:5851,
author = {Eshan Chattopadhyay and David Zuckerman},
title = {{New Extractors for Interleaved Sources}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {7:17:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5851},
URN = {urn:nbn:de:0030drops58513},
doi = {10.4230/LIPIcs.CCC.2016.7},
annote = {Keywords: extractor, derandomization, explicit construction}
}
2016
Keywords: 

extractor, derandomization, explicit construction 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 