Lower bounds on the multiparty communication complexity
type: Item
instance of: scholarly article
title: Lower bounds on the multiparty communication complexity
zbMATH Open document ID: 0917.94024
author: Pavol Ďuriš
author: José Rolim
published in: Journal of Computer and System Sciences
publication date: 1998-12-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 1210195
zbMATH Keywords: algorithmic information theory
zbMATH Keywords: lower bounds
zbMATH Keywords: multiparty communication complexity
zbMATH Keywords: Boolean functions
reviewed by: Eleonor Ciurea
MaRDI profile type: Publication
full work available at URL: jcss.1997.1547
OpenAlex ID: W2016981839
cites work: Lower bounds on communication complexity
cites work: Communication complexity
DOI: 10.1006/JCSS.1997.1547
Recommended article: Optimal lower bounds on the multiparty communication complexity
Recommended article: Communication Complexity and Lower Bounds on Multilective Computations
Recommended article: Q3801064
Recommended article: Lower bounds on communication complexity
Recommended article: Q4601824
Recommended article: Lower Bounds in Communication Complexity
Recommended article: Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
Recommended article: Automata, Languages and Programming
Recommended article: Q5743415
Recommended article: Lower bounds for number-in-hand multiparty communication complexity, made easy
description: scientific article; zbMATH DE number 1210195