Communication Complexity

In this paper we prove several results concerning this complexity measure. First we establish (in a non-constructive manner) that there exist languages which cannot be recognized with less than n communication (obviously, communication n is always enough for recognizing any language). In fact, we show that for any function f(n) < n, there are languages recognizable with communication f(n) but not with communication f (n) -1. In other words, this complexity measure possesses a very dense hierarchy or complexity classes, as miniscule increments in communication add to the languages that can be recognized.

Authors

• Christos H. Papadimitriou
• Michael Sipser

Keywords

No keywords are indexed for this paper.