Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources

Full text

Pdf (908 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents

Providence, Rhode Island, United States

Pages: 366 - 378

Year of Publication: 1985

ISBN:0-89791-151-2

Author

U V Vazirani

University of California, Berkeley, CA

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

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

	Bl1	M. Blum, "Coin Flipping by Telephone," IEEE COMPCON (1982).
	Bl2	M. Blum, "independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov Chain," Proc. 25th Ann. Syrup. on the Theory of Computing, Oct. 1984, 425-433.
	El	P. Elias, "The Efficient Construction of an Unbiased Random Sequence,~' Ann. Math. Statist. Vol 43, No. 3, 1972, 866- 870.
	GM	Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
	KG	W. Kennedy and J. Gentle, Statistical Computing, Marcel Dekker, Inc. New York.
	Kn	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	LS	Richard J. Lipton , Robert Sedgewick, Lower bounds for VLSI, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.300-307, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802482]
	Mu	H.F. Murry, "A general approach for generating natural random variables," IEEE Trans. (;omput., vol. C-19, pp. 1210-1213. Dec 1970.
	vN	J. yon Neumann, '~Various Techniques Used in Connection with Random Digits," Notes by G. E. Forsythe, National Bureau of Standards, Applied Math Series, 1951, Vol 12, 36-38. Reprinted in yon Neumann's Collected Works, Vol 5, Pergamon Press (1963), 768-770.
	PS	Christos H. Papadimitriou , Michael Sipser, Communication complexity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.196-200, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802192]
	Ra	M. Rabin, "Probabilistic Algorithms," Algorithms and Complexity, J.Traub, Editor, Academic Press (t976), pp. 2t- 39.
	Re	A. Renyi, "Probability Theory," North- Holland Series in Applied Mathematics and Mechanics, vol !0, North-Holland Publishing Company, Amsterdam, 1970.
	Ru	W. Rudin, "Principles of Mathematical Analysis," Third Edition, McGraw-Hill Book Company.
	SV	M. Santha and U. V. Vazirani, "Generating Quasi-random Sequences from Slightly-random Sources,~' Proc. 25th Ann. Symp. on the Theory of Computing, Oct. 1984, 434-440.
	Sc	B. Schmeiser, "Random Variate Generation: A Survey," 1980 IEEE. Simulation with Discrete Models: A State-of-the-Art View, T.Oren, C. Shub, P. Roth (eds.).
	VV	U.V. Vazirani and V. V. Vazirani, "Trapdoor Pseudo-random Number Generators with Applications to Protocol Design," Proc. 24th Ann. Symp. on the Theory of Computing, Nov. 1983, 23-30.
	Ya1	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
	Ya2	A. C. Yao, "Lower Bounds by Probabilistic Arguments," Proc. 24 Ann. Syrup on the Theory of Computing, Nov. 1983, 42O-428.

CITED BY 8

	James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998
	L. Babai , N. Nisan, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.1-11, May 14-17, 1989, Seattle, Washington, United States
	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
	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
	D. Lichtenstein , N. Linial , M. Saks, Imperfect random sources and discrete controlled processes, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.169-177, January 1987, New York, New York, United States
	James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.559-568, May 04-06, 1997, El Paso, Texas, United States
	Anup Rao, Extractors for a constant number of polynomially small min-entropy independent sources, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Boaz Barak , Anup Rao , Ronen Shaltiel , Avi Wigderson, 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA