ECCC-Report TR18-110https://eccc.weizmann.ac.il/report/2018/110Comments and Revisions published for TR18-110en-usTue, 11 Sep 2018 22:12:53 +0300
Revision 1
| Improved Extractors for Recognizable and Algebraic Sources |
Fu Li,
David Zuckerman
https://eccc.weizmann.ac.il/report/2018/110#revision1We 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.Tue, 11 Sep 2018 22:12:53 +0300https://eccc.weizmann.ac.il/report/2018/110#revision1
Paper TR18-110
| Improved Extractors for Recognizable and Algebraic Sources |
Fu Li,
David Zuckerman
https://eccc.weizmann.ac.il/report/2018/110We 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.Mon, 04 Jun 2018 21:34:59 +0300https://eccc.weizmann.ac.il/report/2018/110