BenAroya, Avraham ;
Cohen, Gil ;
Doron, Dean ;
TaShma, Amnon
TwoSource Condensers with Low Error and Small Entropy Gap via EntropyResilient Functions
Abstract
In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a twosource extractor with error epsilon for nbit sources having minentropy {polylog}(n/epsilon). Unfortunately, the construction's runningtime is {poly}(n/epsilon), which means that with polynomialtime constructions, only polynomiallysmall errors are possible. Our main result is a {poly}(n,log(1/epsilon))time computable twosource condenser. For any k >= {polylog}(n/epsilon), our condenser transforms two independent (n,k)sources to a distribution over m = kO(log(1/epsilon)) bits that is epsilonclose to having minentropy m  o(log(1/epsilon)). Hence, achieving entropy gap of o(log(1/epsilon)).
The bottleneck for obtaining low error in recent constructions of twosource extractors lies in the use of resilient functions. Informally, this is a function that receives input bits from r players with the property that the function's output has small bias even if a bounded number of corrupted players feed adversarial inputs after seeing the inputs of the other players. The drawback of using resilient functions is that the error cannot be smaller than ln r/r. This, in return, forces the running time of the construction to be polynomial in 1/epsilon.
A key component in our construction is a variant of resilient functions which we call entropyresilient functions. This variant can be seen as playing the above game for several rounds, each round outputting one bit. The goal of the corrupted players is to reduce, with as high probability as they can, the minentropy accumulated throughout the rounds. We show that while the bias decreases only polynomially with the number of players in a oneround game, their success probability decreases exponentially in the entropy gap they are attempting to incur in a repeated game.
BibTeX  Entry
@InProceedings{benaroya_et_al:LIPIcs:2019:11258,
author = {Avraham BenAroya and Gil Cohen and Dean Doron and Amnon TaShma},
title = {{TwoSource Condensers with Low Error and Small Entropy Gap via EntropyResilient Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {43:143:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11258},
URN = {urn:nbn:de:0030drops112587},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.43},
annote = {Keywords: Condensers, Extractors, Resilient functions, Explicit constructions}
}
17.09.2019
Keywords: 

Condensers, Extractors, Resilient functions, Explicit constructions 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 