Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Ben-Aroya, Avraham; Chattopadhyay, Eshan; Doron, Dean; Li, Xin; Ta-Shma, Amnon http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-88877
URL:

; ; ; ;

A New Approach for Constructing Low-Error, Two-Source Extractors

pdf-format:


Abstract

Our main contribution in this paper is a new reduction from explicit two-source extractors for polynomially-small entropy rate and negligible error to explicit t-non-malleable extractors with seed-length that has a good dependence on t. Our reduction is based on the Chattopadhyay and Zuckerman framework (STOC 2016), and surprisingly we dispense with the use of resilient functions which appeared to be a major ingredient there and in follow-up works. The use of resilient functions posed a fundamental barrier towards achieving negligible error, and our new reduction circumvents this bottleneck. The parameters we require from t-non-malleable extractors for our reduction to work hold in a non-explicit construction, but currently it is not known how to explicitly construct such extractors. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. Nonetheless, we believe our work gives a viable approach for solving the important problem of low-error two-source extractors. Furthermore, our work highlights an existing barrier in constructing low-error two-source extractors, and draws attention to the dependence of the parameter t in the seed-length of the non-malleable extractor. We hope this work would lead to further developments in explicit constructions of both non-malleable and two-source extractors.

BibTeX - Entry

@InProceedings{benaroya_et_al:LIPIcs:2018:8887,
  author =	{Avraham Ben-Aroya and Eshan Chattopadhyay and Dean Doron and Xin Li and Amnon Ta-Shma},
  title =	{{A New Approach for Constructing Low-Error, Two-Source Extractors}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8887},
  URN =		{urn:nbn:de:0030-drops-88877},
  doi =		{10.4230/LIPIcs.CCC.2018.3},
  annote =	{Keywords: Two-Source Extractors, Non-Malleable Extractors, Pseudorandomness, Explicit Constructions}
}

Keywords: Two-Source Extractors, Non-Malleable Extractors, Pseudorandomness, Explicit Constructions
Seminar: 33rd Computational Complexity Conference (CCC 2018)
Issue date: 2018
Date of publication: 2018


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