Spring 2017

Improved Extractors for Recognizable and Algebraic Sources

Monday, Jun. 18, 2018 3:45 pm4:15 pm

Add to Calendar

We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources. Our first method shows that if C admits XOR amplification, then we can construct a seedless extractor for C-recognizable sources by using a mildly hard function for C as a black box. By exploiting this reduction, we give polynomial-time, seedless randomness extractors for algebraic sources over any prime field, where algebraic sources are uniform distributions over the set of solutions of a system of low degree polynomials. In particular, the new extractor has linear output length and exponentially small error for min-entropy k ? (1 ? ?)n, where ? > 0 is a small enough constant. Our second method shows that a seed-extending pseudorandom generator with exponentially small error for C yields an extractor with exponentially small error for C-recognizable sources, improving a reduction by Kinne, Melkebeek, and Shaltiel [KvMS12]. Using the hardness of the parity function against AC0 [H?as87], we significantly improve Shaltiel?s extractor [Sha11] for AC0 -recognizable sources. Finally, assuming sufficiently strong one-way permutations, we construct seedless extractors for sources recognizable by BPP algorithms, and these extractors run in quasi-polynomial time.

Joint work with David Zuckerman.