Randomness-optimal sampling, extractors, and constructive leader election

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomness-optimal sampling, extractors, and constructive leader election

Full text

Pdf (947 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 286 - 295

Year of Publication: 1996

ISBN:0-89791-785-5

Author

David Zuckerman

Dept. of Computer Sciences, The University of Texas at Austin, Austin, TX

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 18, Citation Count: 6

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

	AKS87	M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
	AN93	Noga Alon , Moni Naor, Coin-flipping games immune against linear-sized coalitions, SIAM Journal on Computing, v.22 n.2, p.403-417, April 1993 [doi>10.1137/0222030]
	AW	R. Armoni and A. Wigderson. Pseudorandomness for space-bounded computations. Unpublished manuscript.
	BGG93	Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Randomness in interactive proofs, Computational Complexity, v.3 n.4, p.319-354, Oct. 1993 [doi>10.1007/BF01275487]
	Blu86	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]
	BN	R. Boppana and B. Narayanan. Perfectinformation leader election with optimal resilience. Unpublished manuscript.
	BR94	M. Bellare and J. Rompel. Randomnessefficient oblivious sampling. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 276-287, 1994.
	CEG95	Ran Canetti , Guy Even , Oded Goldreich, Lower bounds for sampling algorithms for estimating the average, Information Processing Letters, v.53 n.1, p.17-25, Jan. 13, 1995 [doi>10.1016/0020-0190(94)00171-T]
	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]
	CG89	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]
	CGH+85	B. Chor, O. Goldreich, J. H~stad, J. Friedman, S. Rudich, and R. Smolensky. The bit extraction problem or t-resilient functions. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pages 396-407, 1985.`
	CL93	Jason Cooper , Nathan Linial, Fast perfection-information leader-election protocol with linear immunity, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.662-671, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167258]
	CW89	A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 14-19, 1989.
	FM88	Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62225]
	IZ89	R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 248-253, 1989.
	Lub86	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	Nis92	N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorlea, 12(4):449-461, 1992.
	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]
	ORV94	Rafail Ostrovsky , Sridhar Rajagopalan , Umesh Vazirani, Simple and efficient leader election in the full information model, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.234-242, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195141]
	Sak89	Michael Saks, A robust noncrytographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics, v.2 n.2, p.240-244, May 1989 [doi>10.1137/0402020]
	San87	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]
	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]
	SSZ95	Michael Saks , Aravind Srinivasan , Shiyu Zhou, Explicit dispersers with polylog degree, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.479-488, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225188]
	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 Annual IEEE Symposium on Foundations of Computer Science, pages 264-275, 1994.
	Ta-S96	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]
	WZ95	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]
	Zuc90	D. Zuckerman. General weak random sources. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 534-543, 1990.
	Zuc91	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]

CITED BY 6

	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
	Roy Armoni , Amnon Ta-Shma , Avi Widgerson , Shiyu Zhou, An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs, Journal of the ACM (JACM), v.47 n.2, p.294-311, March 2000
	Roy Armoni , Amnon Ta-Shma , Avi Wigderson , Shiyu Zhou, SL ⊆L^4/3, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.230-239, May 04-06, 1997, El Paso, Texas, United States
	Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001
	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
	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

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

General Terms:
Theory, Verification

Collaborative Colleagues:

David Zuckerman: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player