Extracting all the randomness and reducing the error in Trevisan's extractors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Extracting all the randomness and reducing the error in Trevisan's extractors

Full text

Pdf (870 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: 149 - 158

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Ran Raz	Department of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot, 76100 Israel
Omer Reingold	Department of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot, 76100 Israel
Salil Vadhan	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 17, Citation Count: 15

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.301292 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.

	ACR97	Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.177-187, July 07-11, 1997
	AK92	E. F. Assmus, Jr., Designs and their codes, Cambridge University Press, New York, NY, 1992
	AKSS89	Mikl6s Ajtai, J,'fnos Koml6s, William Steiger, and Endre Szemer6di. Almost sorting in one round. In Sitrio Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 117- 125. JAl Press Inc., 1989.
	ASE92	Noga Alon, Joel H. Spencer, and Paul Erd6s. The Probabifistic Method. Wiley-lnterscience Series in Discrete Mathematics and Optimization. John Wiley and Sons, Inc., 1992.
	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]
	GW97	Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties: a quality-size trade-off for hashing, Random Structures & Algorithms, v.11 n.4, p.315-343, Dec. 1997
	GZ97	Oded Goldreich and David Zuckerman. Another proof that BPP _C PH (and more). Electronic Colloquium on Computational Complexity Technical Report TR97-045, September 1997. http'//www, eccc .uni-trSer.de/eccc.
	ILL89	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	MR95	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	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
	NT98	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]
	NZ96	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]
	Pip87	Nicholas Pippenger, Sorting and selecting in rounds, SIAM Journal on Computing, v.16 n.6, p.1032-1038, December 1, 1987 [doi>10.1137/0216066]
	RR99	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 [doi>10.1145/301250.301294]
	RT97	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
	Sip88	Michael Siper, Expanders, randomness, or time versus space, Journal of Computer and System Sciences, v.36 n.3, p.379-383, June 1988 [doi>10.1016/0022-0000(88)90035-9]
	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]
	STV98	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]
	SZ98	Aravind Srinivasan , David Zuckerman, Computing with Very Weak Random Sources, SIAM Journal on Computing, v.28 n.4, p.1433-1459, Aug. 1999 [doi>10.1137/S009753979630091X]
	Tre98	Luca Trevisan. Constructions of near-optimal extractors using pseudo-random generators. Electronic Colloquium on Computational Complexity Technical Report TR98-55, September I998. Extended abstract in these proceedings.
	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]
	TS98a	Amnon Ta-Shma. Personal communication, August 1998.
	TS98b	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]
	Vaz84	Umesh V. Vazirani. Randomness, Adversaries, and Computation. PhD thesis, University of California, Berkeley, 1984.
	Vaz87a	U. Vazirani, Efficiency considerations in using semi-random sources, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.160-168, January 1987, New York, New York, United States [doi>10.1145/28395.28413]
	Vaz87b	Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
	VV85	Umesh V. Vazirani and Vijay V. Vazirani. Random polynomial time is equal to slightly-random polynomial time. In 26th Annual Symposium on Foundations of Computer Science, pages 417-428, Portland, Oregon, 21-23 October 1985. IEEE.
	WZ95	David Zuckerman , Avi Wigderson, Expanders that Beat the Eigenvalue Bound: Explicit Construction andApplications, University of Texas at Austin, Austin, TX, 1995
	Yao82	Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80- 9 t, Chicago, Illinois, 3-5 November 1982. IEEE.
	Zuc96	David Zuckerman. Simulating BPP using a general weak random source. Algorithmica, t6(4/5):367-391, October/November 1996.
	Zuc97	David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

CITED BY 15

	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
	Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
	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
	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
	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
	Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001
	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 , David Zucherman, Extractor codes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.193-199, July 2001, Hersonissos, Greece
	William Gasarch , Evan Golub , Clyde Kruskal, Constant time parallel sorting: an empirical view, Journal of Computer and System Sciences, v.67 n.1, p.63-91, August 2003
	Tzvika Hartman , Ran Raz, On the distribution of the number of roots of polynomials and explicit weak designs, Random Structures & Algorithms, v.23 n.3, p.235-263, October 2003
	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
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
	Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Piotr Indyk, Uncertainty principles, extractors, and explicit embeddings of l2 into l1, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA