The BNS-Chung criterion for multi-party communication complexity

The "Number on the Forehead" model of multi-party communication complexity was first suggested by Chandra, Furst and Lipton. The best known lower boun d, for an explicit function (in this model), is a lower bound of T (n/2(k)) , where n is the size of the input of each player, and k is the number of p layers (first proved by Babai, Nisan and Szegedy). This lower bound has man y: applications in complexity theory. Proving a better lower bound, for an explicit function, is a major open problem. Based on the result of BNS, Chu ng gave a sufficient criterion for a function to have large multi-party com munication complexity (up to Omega (n/2(k))). In this paper, we use some of the ideas of BNS and Chung, together with some new ideas, resulting in a n ew (easier and more modular) proof for the results of BNS and Chung. This g ives a simpler way to prove lower bounds for the multi-party communication complexity of a function.