Optimal lower bounds on the multiparty communication complexity

DOI10.1007/3-540-59042-0_87MaRDI QIDQ4596635zbMATH OpenOpenAlexFDO

Authors Pavol Ďuriš, José Rolim

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_87

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Lower bounds on the multiparty communication complexity
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Upper bounds on multiparty communication complexity of shifts
• Partition arguments in multiparty communication complexity
• Lower bounds for number-in-hand multiparty communication complexity, made easy

Cited in

(16)

• scientific article; zbMATH DE number 6146451 (Why is no real title available?)
• Multiparty communication complexity and very hard functions
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• scientific article; zbMATH DE number 1419257 (Why is no real title available?)
• Construction of Very Hard Functions for Multiparty Communication Complexity
• Upper bounds on multiparty communication complexity of shifts
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• scientific article; zbMATH DE number 1304094 (Why is no real title available?)
• Languages with Bounded Multiparty Communication Complexity
• The BNS lower bound for multi-party protocols is nearly optimal
• Communication Complexity of Simultaneous Messages
• Lower bounds in communication complexity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• Lower bounds on the multiparty communication complexity
• Automata, Languages and Programming

This page was built for publication: Optimal 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 Q4596635)