|
Abstract : |
The "Number on the Forehead " model of multi-party communication complexity was first suggested by Chandra, Furst and Lipton. The best known lower bound, for an explicit function (in this model), is a lower bound of \Omega\Gamma n=2 k), where n is the size of the input of each player, and k is the number of players (first proved by Babai, Nisan and Szegedy). This lower bound has many applications in complexity theory. Proving a better lower bound, for an explicit function, is a major open problem. Based on the result of BNS, Chung gave a sufficient criterion for a function to have large multi-partycommunication-complexity (up to \Omega\Gamma n=2 k)). In this paper, we use some of the ideas of BNS, and Chung, together with some new ideas, resulting in a new (easier and more modular) proof for the results of BNS and Chung. This gives a simpler way to prove lower bounds for the multi-party-communication-complexity of a function. 1 Multi-Party Communication Complexity Multi-party communication complexity was first introduced by Chandra, Furst and Lipton [CFL], as a generalization of Yao's standard 2-parties communication model [Yao1]. In the k-parties model, we have k finite sets X 1; : : : ; X k, and a function f: X 1 \Theta \Delta \Delta \Delta \Theta X k! f\Gamma1; 1g. We assume w.l.o.g. that X 1 = \Delta \Delta \Delta = X k = f0; 1g, |
