The power of randomness for communication complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The power of randomness for communication complexity

Full text

Pdf (301 KB)

Source

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

New York, New York, United States

Pages: 178 - 181

Year of Publication: 1987

ISBN:0-89791-221-7

Author

M. Furer

Institut für Angewandte Mathematik, Universität Zürich, CH-80011 Zürich/Switzerland

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 16, Citation Count: 4

Additional Information:

abstract 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/28395.28415 What is a DOI?

ABSTRACT

Improving a result of Mehlhorn and Schmidt, a function f with deterministic communication complexity n2 is shown to have Las Vegas communication complexity &Ogr;(n). This is the best possible, because the deterministic complexity cannot be more than the square of the Las Vegas communication complexity for any function.

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	Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983 [doi>10.1145/800061.808742]
	2	Hardy & Wright (1979), An Introduction to the Theory of Numbers, 5th ed., Oxford.
	3	Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
	4	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]
	5	Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]

CITED BY 4

	Paul Beame , Joan Lawry, Randomized versus nondeterministic communication complexity, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.188-199, May 04-06, 1992, Victoria, British Columbia, Canada
	Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece
	T. S. Jayram , Ravi Kumar , D. Sivakumar, Two applications of information complexity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Pavol Ďuriš, Multiparty communication complexity and very hard functions, Information and Computation, v.192 n.1, p.1-14, 1 July 2004