Explicit dispersers with polylog degree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Explicit dispersers with polylog degree

Full text

Pdf (1.19 MB)

Source

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

Las Vegas, Nevada, United States

Pages: 479 - 488

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Michael Saks	Department of Mathematics, Rutgers University, New Brunswick, NJ
Aravind Srinivasan	School of Mathematics, Institute for Advanced Study, Princeton, NJ
Shiyu Zhou	Department of Computer Science, Rutgers University, New Brunswick, NJ

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): 8, Citation Count: 3

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/225058.225188 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	M Blum, Independent unbiased coin flips from a correlated biased source:80a finite state Markov chain, Combinatorica, v.6 n.2, p.97-108, 1986 [doi>10.1007/BF02579167]
	2	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]
	3	A. Cohen and A. Wlgderson, "Dispersers, Deter-ministic Amplification, and Weak Random Sources,n Proc. IEEE Symposium on Foundations of Computer Science, 1989, pp. 14-19.
	4	A. M. Ferrenberg, D. P. Landau, and Y. J. Wong, "Monte Carlo simulations: Hidden errors from 'good" random number generators," Physical Re-view Letters, 69(23):3382-3384, 1992.
	5	Amos Fiat , Moni Naor, Implicit O(1) probe search, SIAM Journal on Computing, v.22 n.1, p.1-10, Feb. 1993 [doi>10.1137/0222001]
	6	T.-s. Hsu, V. Rarnachandran, and N. Dean, "Par-allel implementation of algorithms for finding con-nected components," Proc. DIMA CS International Algorithm Implementation Challenge, 1994, pp. l- 14.
	7	Tsan-Sheng Hsu, Graph augmentation and related problems: theory and practice, University of Texas at Austin, Austin, TX, 1993
	8	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]
	9	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]
	10	Miklos Santha, On using deterministic functions to reduce randomness in probabilistic algorithms, Information and Computation, v.74 n.3, p.241-249, Sept. 1987 [doi>10.1016/0890-5401(87)90023-X]
	11	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]
	12	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]
	13	A. Sriniv~an and D. Zuckerman, 'Computing with Very Weak Random Sources", Proc. IEEE Sympo-sium on Foundations of Computer Science, 1994, pp. 264-275.
	14	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]
	15	Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986
	16	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]
	17	Umesh V. Vazirani , Vijay V. Vazirani, Random Polynomial Time is Equal to Semi-Random Polynomial Time, Cornell University, Ithaca, NY, 1988
	18	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]
	19	D. Zuckerman, "General Weak Random Sources," Proc. IEEE Symposium on Foundations of Computer Science, 1990, pp. 534543.
	20	David Zuckerman, Simulating BPP using a general weak random source, Proceedings of the 32nd annual symposium on Foundations of computer science, p.79-89, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185351]
	21	D. Zuckerman, "NP-complete problems have a ver-sion that's hard to approximate,n Proc. IEEE Con-ference on Structure in Complexity Theory, 1993, pp. 305-312.

CITED BY 3

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