ISSN:
1420-8954
Keywords:
Keywords. Communication complexity, discrepancy.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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(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-party communication 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 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00001602
Permalink