Shaltiel, Ronen and Umans, Christopher (2001) Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. In: 42nd Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 648-657. ISBN 0-7695-1390-5. https://resolver.caltech.edu/CaltechAUTHORS:20111121-092803461
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111121-092803461
Abstract
We present a simple, self-contained extractor construction that produces good extractors for all min-entropies (min-entropy measures the amount of randomness contained in a weak random source). Our construction is algebraic and builds on a new polynomial-based approach introduced by A. Ta-Shma et al. (2001). Using our improvements, we obtain, for example, an extractor with output length m = k^(1-δ) and seed length O(log n). This matches the parameters of L. Trevisan's (1999) breakthrough result and additionally achieves those parameters for small min-entropies k. Our construction gives a much simpler and more direct solution to this problem. Applying similar ideas to the problem of building pseudo-random generators, we obtain a new pseudo-random generator construction that is not based on the NW generator (N. Nisan and A. Widgerson, 1994), and turns worst-case hardness directly into pseudo-randomness. The parameters of this generator are strong enough to obtain a new proof that P=BPP if E requires exponential size circuits. Essentially, the same construction yields a hitting set generator with optimal seed length that outputs s^(Ω(1)) bits when given a function that requires circuits of size s (for any s). This implies a hardness versus randomness trade off for RP and BPP that is optimal (up to polynomial factors), solving an open problem raised by R. Impagliazzo et al. (1999). Our generators can also be used to derandomize AM in a way that improves and extends the results of [4, 18, 20].
Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
Additional Information: | © 2001 IEEE. Date of Current Version: 07 August 2002. We thank Henry Cohn, Venkat Guruswami, Valentine Kabanets, Omer Reingold, Muli Safra, Amnon Ta-Shma, Salil Vadhan, Avi Wigderson and David Zuckerman for helpful discussions. We are especially grateful to the authors of [37] for explaining their result to us. We thank the conference referees for helpful comments. | |||||||||
Other Numbering System: |
| |||||||||
Series Name: | Annual IEEE Symposium on Foundations of Computer Science | |||||||||
DOI: | 10.1109/SFCS.2001.959941 | |||||||||
Record Number: | CaltechAUTHORS:20111121-092803461 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111121-092803461 | |||||||||
Official Citation: | Shaltiel, R.; Umans, C.; , "Simple extractors for all min-entropies and a new pseudo-random generator," Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on , vol., no., pp. 648- 657, 8-11 Oct. 2001 doi: 10.1109/SFCS.2001.959941 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=959941&isnumber=20736 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 27883 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Ruth Sustaita | |||||||||
Deposited On: | 21 Nov 2011 19:00 | |||||||||
Last Modified: | 09 Nov 2021 16:52 |
Repository Staff Only: item control page