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 three natural recognizable sources: (1) constant-degree algebraic sources over any prime field, where constant-degree algebraic sources are uniform distributions over the set of solutions to 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 min-entropy k = (1-c)n, where c > 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 $AC^0$ [Has87], we significantly improve Shaltiel’s extractor [Sha11] for $AC^0$-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.
Added new extractors for sources recognizable by communication protocols and LTFs, and corrected minor typos.
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 \geq (1 - \alpha)n$, where $\alpha > 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 $AC^0$ [Has87], we significantly improve Shaltiel’s extractor [Sha11] for $AC^0$-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.
