The linear-array problem in communication complexity resolved

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The linear-array problem in communication complexity resolved

Full text

Pdf (1.36 MB)

Source

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

El Paso, Texas, United States

Pages: 373 - 382

Year of Publication: 1997

ISBN:0-89791-888-6

Author

Martin Dietzfelbinger

Fachbereich Informatik, Universität Dortmund, D-44221 Dortmund, Germany

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/258533.258622 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	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	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]
	3	Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	4	M. DtETZFELBINGER, The linear array problem in communication complexity resolved, Forschungsbericht Nr. 632, 1996, Fachbereich Informatik, Universit~t Dortmund. Also: Report TR96-063, ECCC, http://w~-w, eccc. uni-trier, de/eccc/.
	5	Bernd Halstenberg , Rüdiger Reischuk, Relations between communication complexity classes, Journal of Computer and System Sciences, v.41 n.3, p.402-429, Dec. 1990 [doi>10.1016/0022-0000(90)90027-I]
	6	Juraj Hromkovič, Communication complexity and parallel computing, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	7	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 [doi>10.1145/237814.238003]
	8	B. KALYANASUNDARAM and G. SCHNITGER, Communication complexity and lower bounds for sequential computation, in J. BUCHMANN et al., eds., Informatik. Festschrift zum 60. Geburtstag yon Giinter Hotz, B. G. Teubner, Stuttgart, 1992, pp. 253-268.
	9	Matthias Krause , Stephan Waack, Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in, Proceedings of the 32nd annual symposium on Foundations of computer science, p.777-782, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185448]
	10	E. KUSHILEVlTZ, personal communication.
	11	Eyal Kushilevitz , Nathan Linial , Rafail Ostrovsky, The linear-array conjecture in communication complexity is false, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.1-10, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237817]
	12	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	13	K. MEHLHORN, Data Structures and Algorithms I: Sorting and Searching, EATCS Monographs on Computer Science, Springer-Verlag, Berlin, 1084.
	14	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]
	15	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]
	16	M.H.A. NEWMAN, On theories with a combinatorial definition of 'equivalence', Ann. Math. 43 (1942) 223- 243.
	17	N. NISAN and A. WIGDERSON, On rank versus communication complexity, Combinatorica 15 (1995) 557-565.
	18	Ramamohan Paturi , Janos Simon, Probabilistic communication complexity, Journal of Computer and System Sciences, v.33 n.1, p.106-123, Aug. 1986 [doi>10.1016/0022-0000(86)90046-2]
	19	A.A. RAZBOROV, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1990) 81-93.
	20	P.M. SPIRA, On time-hardware complexity tradeoffs for Boolean functions, in Proc. of the .ith Hawaii Symposium on System Sciences, 1971, pp. 525-527.
	21	Prasoon Tiwari, Lower bounds on communication complexity in distributed computer networks, Journal of the ACM (JACM), v.34 n.4, p.921-938, Oct. 1987 [doi>10.1145/31846.32978]
	22	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 8

	Yefim Dinitz , Noam Solomon, Two absolute bounds for distributed bit complexity, Theoretical Computer Science, v.384 n.2-3, p.168-183, October, 2007
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Exact communication costs for consensus and leader in a tree, Journal of Discrete Algorithms, v.1 n.2, p.167-183, April 2003
	Meijie Ma , Guizhen Liu , Jun-Ming Xu, Fault-tolerant embedding of paths in crossed cubes, Theoretical Computer Science, v.407 n.1-3, p.110-116, November, 2008
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.265-274, May 01-04, 1999, Atlanta, Georgia, United States
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings, Journal of the ACM (JACM), v.55 n.1, p.1-28, February 2008
	Jianxi Fan , Xiaohua Jia , Xiaola Lin, Optimal Embeddings of Paths with Various Lengths in Twisted Cubes, IEEE Transactions on Parallel and Distributed Systems, v.18 n.4, p.511-521, April 2007
	Jianxi Fan , Xiaohua Jia, Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences: an International Journal, v.178 n.2, p.340-351, January, 2008
	Jianxi Fan , Xiaola Lin , Yi Pan , Xiaohua Jia, Optimal fault-tolerant embedding of paths in twisted cubes, Journal of Parallel and Distributed Computing, v.67 n.2, p.205-214, February, 2007