2026-07-23T04:09:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8887 2024-03-06T10:42:49Z ddc:004 open_access

A New Approach for Constructing Low-Error, Two-Source Extractors Ben-Aroya, Avraham Chattopadhyay, Eshan Doron, Dean Li, Xin Ta-Shma, Amnon Two-Source Extractors Non-Malleable Extractors Pseudorandomness Explicit Constructions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avraham Ben-Aroya and Eshan Chattopadhyay and Dean Doron and Xin Li and Amnon Ta-Shma 2018 Is Part Of LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2018.3 urn:nbn:de:0030-drops-88877 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode