Extractors and pseudo-random generators with optimal seed length

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Extractors and pseudo-random generators with optimal seed length

Full text

Pdf (1.03 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 1 - 10

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Russell Impagliazzo	Computer Science and Engineering, UC, San Diego, 9500 Gilman Drive, La Jolla, CA
Ronen Shaltiel	Department of Computer Science, Hebrew University, Jerusalem, Israel
Avi Wigderson	Department of Computer Science, Hebrew University, Jerusalem, Israel and Institute for Advanced Study, Princeton

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 33, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335306 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	László Babai , Lance Fortnow , Noam Nisan , Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Computational Complexity, v.3 n.4, p.307-318, Oct. 1993 [doi>10.1007/BF01275486]
	2	M. Blum. Independent unbiased coin flips from a correlated biased source: a finite state Markov chain. In 25th Annual Symposium on Foundations of Computer Science, pages 425-433, Singer Island, Florida, 24-26 Oct. 1984. IEEE.
	3	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	4	Jin-Yi Cai , Ajay Nerurkar , D. Sivakumar, Hardness and hierarchy theorems for probabilistic quasi-polynomial time, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.726-735, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301444]
	5	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	6	Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
	7	R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.538, October 23-25, 1995
	8	Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Near-Optimal Conversion of Hardness into Pseudo-Randomness, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.181, October 17-18, 1999
	9	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
	10	R. Impagliazzo , A. Wigderson, Randomness vs. Time: De-Randomization under a Uniform Assumption, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.734, November 08-11, 1998
	11	Adam R. Klivans , Dieter van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.659-667, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301428]
	12	Noam Nisan, Extracting Randomness: How and Why - A survey, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.44, May 24-27, 1996
	13	Naom Nisan , Amnon Ta-Shma, Extracting randomness: a survey and new constructions, Journal of Computer and System Sciences, v.58 n.1, p.148-173, Feb. 1999 [doi>10.1006/jcss.1997.1546]
	14	N. Nisan and A. Wigderson. Hardness vs. randomness (extended abstract), in ~9th Annual Symposium on Foundations of Computer Science, pages 2-11, White Plains, New York, 24-26 Oct. 1988. iEEE.
	15	Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
	16	J. Radhakrishnan , A. Ta-Shma, Tight bounds for depth-two superconcentrators, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.585, October 19-22, 1997
	17	Ran Raz , Omer Reingold , Salil Vadhan, Error Reduction for Extractors, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.191, October 17-18, 1999
	18	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301292]
	19	M. Santha and U. V. Vazirani. Generating quasirandom sequences from slightly-random sources (extended abstract). In ~5th Annual Symposium on Foundations of Computer Science, pages 434-440, Singer Island, Florida, 24-26 Oct. 1984. IEEE.
	20	Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301397]
	21	Luca Trevisan, Construction of extractors using pseudo-random generators (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.141-148, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301289]
	22	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]
	23	A. C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 Nov. 1982. IEEE.

CITED BY 16

	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Journal of Computer and System Sciences, v.65 n.1, p.97-128, August 2002
	Christopher Umans, Pseudo-random generators for all hardnesses, Journal of Computer and System Sciences, v.67 n.2, p.419-440, September 2003
	Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Christopher Umans, Pseudo-random generators for all hardnesses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece
	Dan Gutfreund , Ronen Shaltiel , Amnon Ta-Shma, Uniform hardness versus randomness tradeoffs for Arthur-Merlin games, Computational Complexity, v.12 n.3-4, p.85-130, September 2004
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005
	Peter Bro Miltersen , N. V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, Computational Complexity, v.14 n.3, p.256-279, January 2005
	Amnon Ta-Shma , David Zuckerman , Shmuel Safra, Extractors from Reed-Muller codes, Journal of Computer and System Sciences, v.72 n.5, p.786-812, August 2006
	Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity Via Uniform Reductions, Computational Complexity, v.16 n.4, p.331-364, December 2007
	Zeev Dvir , Amir Shpilka , Amir Yehudayoff, Hardness-randomness tradeoffs for bounded depth arithmetic circuits, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ronen Shaltiel , Christopher Umans, Low-end uniform hardness vs. randomness tradeoffs for AM, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Ronen Shaltiel , Christopher Umans, Pseudorandomness for Approximate Counting and Sampling, Computational Complexity, v.15 n.4, p.298-341, December 2006
	Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes, Journal of the ACM (JACM), v.56 n.4, p.1-34, June 2009