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.2018.3
URN: urn:nbn:de:0030-drops-88877
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8887/
Ben-Aroya, Avraham ;
Chattopadhyay, Eshan ;
Doron, Dean ;
Li, Xin ;
Ta-Shma, Amnon
A New Approach for Constructing Low-Error, Two-Source Extractors
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 f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://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 |
|
Collection: |
|
33rd Computational Complexity Conference (CCC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
