Communication complexity of multi-processor systems

DOI10.1016/0020-0190(89)90110-5MaRDI QIDQ1118403zbMATH OpenOpenAlexFDO

Authors Rudolf Fleischer

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90110-5

zbMATH Keywords

communicating processorscommunication complexityLas Vegas computationsmulti-processor systemsnondeterministic computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication theory (94A05) Applications of graph theory to circuits and networks (94C15)

Review text

The communication complexity model of two communicating processors [\textit{H. Abelson}, J. Assoc. Comput. Mach. 27, 384-392 (1980; Zbl 0438.68009); \textit{Ch. Papadimitriou} and \textit{M. Sipser}, Communication complexity. J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064); \textit{A. C. Yao}, Some complexity questions related to distributive computing, in: Proc. 11th ACM STOC, ACM, 209-213 (1979)], is generalized to a model consisting of k processors connected by a common bus. A lower bound technique used for the original communication complexity is extended for k-processor model and it is shown that the deterministic communication complexity cannot differ more than quadratically from the nondeterministic complexity.

Recommendations

• scientific article; zbMATH DE number 3881884
• Lower bounds on communication complexity
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• Lower bounds on communication complexity in distributed computer networks
• Communication Complexity

Cites work

• Communication complexity
• Distributed algorithms in synchronous broadcasting networks
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• Information Transfer under Different Sets of Protocols
• Lectures on the complexity of bilinear problems
• Lower bounds on communication complexity in distributed computer networks
• Probabilistic communication complexity
• Rank and optimal computation of generic tensors

Cited in

(6)

• On multi-partition communication complexity
• scientific article; zbMATH DE number 3881884 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1121984 (Why is no real title available?)
• scientific article; zbMATH DE number 1795910 (Why is no real title available?)
• scientific article; zbMATH DE number 220134 (Why is no real title available?)

This page was built for publication: Communication complexity of multi-processor systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1118403)