Abstract
We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = 1} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for Crecognizable sources.
Our first method shows that if C admits XOR amplification, then we can construct a seedless extractor for Crecognizable sources by using a mildly hard function for C as a black box. By exploiting this reduction, we give polynomialtime, seedless randomness extractors for three natural recognizable sources: (1) constantdegree algebraic sources over any prime field, where constantdegree algebraic sources are uniform distributions over the set of zeros of a system of constant degree polynomials; (2) sources recognizable by randomized multiparty communication protocols of cn bits, where c>0 is a small enough constant; (3) halfspace sources, or sources recognizable by linear threshold functions. In particular, the new extractor for each of these three sources has linear output length and exponentially small error for minentropy k >= (1alpha)n, where alpha>0 is a small enough constant.
Our second method shows that a seedextending pseudorandom generator with exponentially small error for C yields an extractor with exponentially small error for Crecognizable sources, improving a reduction by Kinne, Melkebeek, and Shaltiel [Kinne et al., 2012]. Using the hardness of the parity function against AC^0 [HÃ¥stad, 1987], we significantly improve Shaltiel's extractor [Shaltiel, 2011] for AC^0recognizable sources. Finally, assuming sufficiently strong oneway permutations, we construct seedless extractors for sources recognizable by BPP algorithms, and these extractors run in quasipolynomial time.
BibTeX  Entry
@InProceedings{li_et_al:LIPIcs:2019:11287,
author = {Fu Li and David Zuckerman},
title = {{Improved Extractors for Recognizable and Algebraic Sources}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {72:172:22},
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/11287},
URN = {urn:nbn:de:0030drops112873},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.72},
annote = {Keywords: Extractor, Pseudorandomness}
}
Keywords: 

Extractor, Pseudorandomness 
Collection: 

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

2019 
Date of publication: 

17.09.2019 