Rounds in communication complexity revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rounds in communication complexity revisited

Full text

Pdf (649 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 419 - 429

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Noam Nisan	Hebrew Univ., Jerusalem, Israel
Avi Widgerson	Hebrew Univ., Jerusalem, Israel

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): 27, Citation Count: 4

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/103418.103463 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	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 [doi>10.1145/73007.73008]
	2	Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
	3	L. Carter, M. Wegman: Universal hash functions Journal of Comp. and Sys. Sci. 18 (1979) 143-154.
	4	Pavol Duris , Zvi Galil , Georg Schnitger, Lower bounds on communication complexity, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.81-91, December 1984 [doi>10.1145/800057.808668]
	5	M. Goldman, J. Hastad: On t,#e power of small depth threshold circuits Proe. of the 31st FOCS, (1990) 610-618.
	6	Bernd Halstenberg , Rudiger Reischuk, On different modes of communication, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.162-172, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62226]
	7	Maria Klawe , Wolfgang J. Paul , Nicholas Pippenger , Mihalis Yannakakis, On monotone formulae with restricted depth, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.480-487, December 1984 [doi>10.1145/800057.808717]
	8	Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62265]
	9	T. Lam, L. Ruzzo: Results on Communication Complexity Classes Proc. of the 4th Structures in Complexity Theory conference, (1989) 148-157.
	10	L.A. McGeoch: A Strong Seperation Between k and k-1 Round Communication Complexity for a Constructive Language CMU Technical Report CMU-CS-86-157 (1986)
	11	Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100246]
	12	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]
	13	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	14	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]
	15	R. Raz, A. Wigderson: Probabilistic Communication Complexity of Boolean Relations Proc. of the 30th FOCS, (1989) 562-567
	16	D. V. Smirnov: Shannon's information methods for lower bounds for probabilistic communication complexity, Manuscript (in Russian)(1989)
	17	L. Valiant: Graph theoretic arguments in low-level complexity Technical Report CS 13-77, University of Edinburgh (1977).
	18	M. Yanakakis: Private communication.
	19	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]
	20	A.C.-C. Yao: Lower Bounds by Probabilistic Arguments Proc of the 24th FOCS, (1983) 420-428

CITED BY 4

	J. Hromkovic , G. Schnitger, Nondeterministic communication with a limited number of advice bits, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.551-560, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Mario Szegedy , Xiaomin Chen, Computing Boolean functions from multiple faulty copies of input bits, Theoretical Computer Science, v.321 n.1, p.149-170, June 16, 2004
	P. Pudlák , V. Rödl, Modified ranks of tensors and the size of circuits, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.523-531, May 16-18, 1993, San Diego, California, United States
	Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia