Lower bounds on the multiparty communication complexity (Q1267715)

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.