License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.7
URN: urn:nbn:de:0030-drops-58513
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5851/
Go to the corresponding LIPIcs Volume Portal

Chattopadhyay, Eshan ; Zuckerman, David

New Extractors for Interleaved Sources

pdf-format:
30.pdf (0.6 MB)

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:

(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.

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:1--7:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Ran Raz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5851},
  URN =		{urn:nbn:de:0030-drops-58513},
  doi =		{10.4230/LIPIcs.CCC.2016.7},
  annote =	{Keywords: extractor, derandomization, explicit construction}
}

Keywords: extractor, derandomization, explicit construction
Collection: 31st Conference on Computational Complexity (CCC 2016)
Issue Date: 2016
Date of publication: 19.05.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI