The BNS-Chung criterion for multi-party communication complexity

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

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 Ω(n/2k), 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 Ω(n/2k)). 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.

Original languageEnglish (US)
Pages (from-to)113-122
Number of pages10
JournalComputational Complexity
Volume9
Issue number2
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Communication complexity
  • Discrepancy

Fingerprint Dive into the research topics of 'The BNS-Chung criterion for multi-party communication complexity'. Together they form a unique fingerprint.

Cite this