Construction of extractors using pseudo-random generators (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Construction of extractors using pseudo-random generators (extended abstract)

Full text

Pdf (686 KB)

Source

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

Atlanta, Georgia, United States

Pages: 141 - 148

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Luca Trevisan

Computer Science Department, Columbia University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 19, Citation Count: 7

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/301250.301289 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.

	ACRT97	A. E. Andreev , A. E. F. Clementi , J. D. P. Rolim , L. Trevisan, Weak random sources, hitting sets, and BPP simulations, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.264, October 19-22, 1997
	AR98	E. Allender and K. Reinhardt. Isolation, matching, and counting. Technical Report TR98-019, Electronic Colloquium on Computational Complexity, 1998.
	BFNW93	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]
	BGS98	Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
	BM84	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]
	BR94	M. Bellare a~d J. Rompel. Randomness-efficient oblivious sampling. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 276-287, 1994.
	CG88	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	CW89	A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 14-19, 1989.
	GM84	S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-299, 1984. Preliminary Version in Proc. of STOC'8~.
	GNW95	O. Gotdreich, N. Nisan, and A. Wigderson. On Yao's XOR lemma. Technical Report TR95-50, Electronic Colloquium on Computational Complexity, 1995.
	Gol99	Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
	GZ97	O. Goldreich and D. Zuckerman. Another proof that BPP C_ PH (and more). Technical Report TR97-045, Electronic Colloquium on Computational Complexity, 1997.
	Imp95	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
	IW97	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]
	IW98	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
	MS77	F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
	Nis96	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
	NTS98	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]
	NW94	Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
	NZ93	Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167162]
	RRV99	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]
	RTS97	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
	SSZ98	Michael Saks , Aravind Srinivasan , Shiyu Zhou, Explicit OR-dispersers with polylogarithmic degree, Journal of the ACM (JACM), v.45 n.1, p.123-154, Jan. 1998 [doi>10.1145/273865.273915]
	STV99	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]
	SV86	Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
	SZ94	A. Srinivasan and D. Zuckerman. Computing with very weak random sources. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 264-275, 1994.
	TS96	Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237877]
	TS98	Amnon Ta-Shma, Almost optimal dispersers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.196-202, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276736]
	VV85	U. Vazirani and V. Vazirani. Random polynomial time is equal to slightly random polynomial time. In Proceedings of the B6th IEEE Symposium on Foundations of Computer Science, pages 417-428, t 985.
	WZ93	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]
	Yao82	A.C. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23th IEEE Symposium on Foundations of Computer Science, pages 80-91, 1982.
	Zuc90	D. Zuckerman. General weak random sources. In Proceedings of the 31st {EEE Symposium on Foundations of Computer Science, pages 534- 5z13, 1990.
	Zuc96a	David Zuckerman, On Unapproximable Versions of NP-Complete Problems, SIAM Journal on Computing, v.25 n.6, p.1293-1304, Dec. 1996 [doi>10.1137/S0097539794266407]
	Zuc96b	David Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.286-295, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237878]

CITED BY 7

	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 , David Zucherman, Extractor codes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.193-199, July 2001, Hersonissos, Greece
	Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Extractors and pseudo-random generators with optimal seed length, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.1-10, May 21-23, 2000, Portland, Oregon, United States
	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
	Ran Raz , Omer Reingold, On recycling the randomness of states in space bounded computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.159-168, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002