Public vs. private coin flips in one round communication games (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Public vs. private coin flips in one round communication games (extended abstract)

Full text

Pdf (832 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: 561 - 570

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Ilan Newman	Dept. of Mathematics and Comp. Sci, Haifa U, Israel
Mario Szegedy	AT&T Bell Labs

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 22, Citation Count: 10

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.238004 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	J. Bourgain and A. Wigderson, Personal communication.
	2	Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.596-605, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225277]
	3	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	4	L. Lovisz, Communication complexity: a survey, in Path flowers and VLSI, (Ed, B. Korte, L.Lovksz, A. Schrijver, ), Springer Verlag, 1990.
	5	Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
	6	Mihalis Yannakakis, Expressing combinatorial optimization problems by linear programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.223-228, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62232]
	7	A. C. Yao, Probabilistic compulation, towards a unified measure of complexity, Proc. 18th IEEE Syrup. on Foundation of Computer Science, (1977), pp. 222-227.
	8	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]

CITED BY 10

	Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece
	Andrew Chi-Chih Yao, On the power of quantum fingerprinting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002
	Phillip B. Gibbons , Srikanta Tirthapura, Distributed streams algorithms for sliding windows, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Ziv Bar-Yossef , T. S. Jayram , Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Dmitry Gavinsky , Julia Kempe , Oded Regev , Ronald de Wolf, Bounded-error quantum state identification and exponential separations in communication complexity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Wei Huang , Yaoyun Shi , Shengyu Zhang , Yufan Zhu, The communication complexity of the Hamming distance problem, Information Processing Letters, v.99 n.4, p.149-153, 31 August 2006
	Jon Feldman , S. Muthukrishnan , Anastasios Sidiropoulos , Cliff Stein , Zoya Svitkina, On distributing symmetric streaming computations, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.710-719, January 20-22, 2008, San Francisco, California
	Ilya Mironov , Moni Naor , Gil Segev, Sketching in adversarial environments, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Moni Naor , Guy N. Rothblum, The complexity of online memory checking, Journal of the ACM (JACM), v.56 n.1, p.1-46, January 2009