Lower bounds on the multiparty communication complexity

DOI10.1006/JCSS.1997.1547MaRDI QIDQ1267715zbMATH OpenOpenAlexFDO

Authors Pavol Ďuriš, José Rolim

Publication date 8 December 1998

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1997.1547

zbMATH Keywords

lower boundsBoolean functionsalgorithmic information theorymultiparty communication complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Optimal lower bounds on the multiparty communication complexity
• Communication Complexity and Lower Bounds on Multilective Computations
• scientific article; zbMATH DE number 4068270
• Lower bounds on communication complexity
• Simplified lower bounds on the multiparty communication complexity of disjointness
• Lower bounds in communication complexity
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• Automata, Languages and Programming
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• Lower bounds for number-in-hand multiparty communication complexity, made easy

Cites work

• Communication complexity
• Lower bounds on communication complexity

Cited in

(26)

• Upper bounds on multiparty communication complexity of shifts
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• scientific article; zbMATH DE number 1419257 (Why is no real title available?)
• scientific article; zbMATH DE number 1418336 (Why is no real title available?)
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Construction of Very Hard Functions for Multiparty Communication Complexity
• Partition arguments in multiparty communication complexity
• scientific article; zbMATH DE number 6146451 (Why is no real title available?)
• The BNS-Chung criterion for multi-party communication complexity
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• scientific article; zbMATH DE number 1304094 (Why is no real title available?)
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• Partition Arguments in Multiparty Communication Complexity
• The communication complexity of computing differentiable functions in a multicomputer network
• The effect of range and bandwidth on the round complexity in the congested clique model
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• The Range of Topological Effects on Communication
• Languages with Bounded Multiparty Communication Complexity
• Multiparty communication complexity and very hard functions
• The price of low communication in secure multi-party computation
• Optimal lower bounds on the multiparty communication complexity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• Automata, Languages and Programming
• Multiparty communication complexity of vector-valued and sum-type functions
• Lower bounds in communication complexity
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)

This page was built for publication: Lower bounds on the multiparty communication complexity

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