Lower bounds on the multiparty communication complexity
The authors propose a general technique used to obtain lower bounds on the multiparty communication complexity of Boolean functions.This technique represents an extension of the two party method that was introduced by Yao (1979) for the multiparty communication model. Based on it, optimal upper and lower bounds are found for some Boolean functions. The main result of this article is given by the equation \(C_0\leq n(1+2^{c_1})\), where \(C_1\) and \(C_0\) represent the number of bits exchanged in a non-deterministic algorithm for the functions \(f\) and \(1-f\), respectively. The authors also propose the equation \(D\leq n(1+2^{c_1})\), where \(D\) represents the bits exchanged in a deterministic algorithm for the function \(f\). Finally, the authors investigate the power of a particular multiparty communication model in which the coordinator process is allowed to send at most one message to each process.
- 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
- A three-party communication problem
- The communication complexity of computing differentiable functions in a multicomputer network
- The price of low communication in secure multi-party computation
- A note on multiparty communication complexity and the Hales-Jewett theorem
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- The effect of range and bandwidth on the round complexity in the congested clique model
- Lower bounds in communication complexity
- A direct product theorem for two-party bounded-round public-coin communication complexity
- The Range of Topological Effects on Communication
- Languages with Bounded Multiparty Communication Complexity
- Partition Arguments in Multiparty Communication Complexity
- Determinism vs. Nondeterminism in Multiparty Communication Complexity
- scientific article; zbMATH DE number 1304094 (Why is no real title available?)
- Communication Complexity and Lower Bounds on Multilective Computations
- Construction of Very Hard Functions for Multiparty Communication Complexity
- Upper bounds on multiparty communication complexity of shifts
- Optimal lower bounds on the multiparty communication complexity
- scientific article; zbMATH DE number 6146451 (Why is no real title available?)
- Multiparty communication complexity of vector-valued and sum-type functions
- scientific article; zbMATH DE number 1418336 (Why is no real title available?)
- scientific article; zbMATH DE number 1419257 (Why is no real title available?)
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- Partition arguments in multiparty communication complexity
- Automata, Languages and Programming
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
- The BNS-Chung criterion for multi-party communication complexity
- Multiparty communication complexity and very hard functions
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)
