Communication Complexity ...Classes?

Question

Discussion:

I've been spending some personal time lately learning various things in communication complexity. For instance, I've re-familiarized myself with the relevant chapter in Arora/Barak, started reading some papers, and ordered the book by Kushilevitz/Nisan. Intuitively, I want to contrast communication complexity with computational complexity. And in particular, I'm struck by the fact that computational complexity has developed into a rich theory of placing computational problems into complexity classes, some of which can be in turn (from one perspective, at least) envisioned in terms of complete problems for each given class. For instance, when explaining $NP$ to someone for the first time, it's hard to avoid comparisons to SAT or some other NP-complete problem.

By comparison, I've never heard anything of an analogous concept for communication complexity classes. There are many examples that I'm aware of, of problems "complete for a theorem." For instance, as a general framework, the authors might describe a given communication problem $P$ and then prove that a related theorem $T$ holds $iff$ the communication problem can be solved in $X$ or less bits (for some $X$ that depends on the specific theorem/problem pair in question). The terminology used then in literature is that $P$ is "complete" for $T$.

Further, there is a tantalizing line in the Arora/Barak communication complexity chapter draft (that seems to have been removed/tweaked in the final printing) that states "In general, one can consider communication protocols analogous to $NP$, $coNP$, $PH$ etc." However, I notice two important omissions:

1. The "analogous" concept appears to be a manner of computing the communication complexity of solving a given protocol with access to different types of resources, but stops just short of defining proper communication complexity classes...
2. Most of communication complexity seems to be relatively "low-level," in the sense that the overwhelming majority of results/theorems/etc. revolve around small-ish, specific, polynomial-sized values. This somewhat begs the question of why, say, $NEXP$ is interesting for computation but the analogous concept appears to be less interesting for communication. (Of course, I could just be at fault for simply being unaware of "higher-level" communication complexity concepts.)

---

Question(s):

Is there an analogous concept to computational complexity classes for communication complexity?

And:

If so, how does it compare to the "standard" notion of complexity classes? (e.g. are there natural limitations to "communication complexity classes" that cause them to inherently fall short of the full range of computational complexity classes?) If not, what's the "big picture" reason that classes are an interesting formalism for computational complexity but not for communication complexity?

Answer 1

It seems that you are looking for this paper: http://portal.acm.org/citation.cfm?id=1382439.1382962

Answer 2

Complexity classes in communication complexity were introduced by Babai, Frankl, Simon in the paper quoted by Noam. The paper also develops the idea of completeness under suitable reductions. If you for instance describe the classes NP and co-NP it makes a lot of sense to describe the (co-NP complete) Disjointness problem as well.

As to your second questions, if P is (in communication complexity) the class of problems solvable with polylog(n) communication deterministically, then the class EXP should be the set of problems solvable with poly(n) communication, which simply is everything. So it seems that such classes are not interesting.

However, there is another way to get larger classes. Already PSPACE is defined (by Babai et al.) not in terms of some notion of space, but in terms of alternation. Interactive proofs are another way to get large complexity classes. So you can define the class MIP as the set of problems that can be solved in a communication game with two provers (who cannot talk to each other) and two verifiers (who can talk to each other and to the provers ).

In the Turing machine world, MIP=NEXP, but what about in communication complexity (where NEXP does not seem to make sense)? First of all, MIP is not just the set of all problems due to a simple counting argument.

Andrew Drucker (in his masters thesis) has shown something interesting about this class. He considers PCP's in communication complexity, which (by standard techniques) are equivalent to MIP protocols (his result is a little stronger than what I state here).

What he shows is that for every problem in NP (the Turing machine class) and any way to split up the inputs, the resulting communication problem has an MIP protocol with communication polylog(n) (i.e. the problem is in the (communication complexity) class MIP).

So, while MIP is not everything, finding an explicit problem that is not in MIP should be hard (not because we cannot find problems that are not in NP, but because it is not easy to imagine how the Turing machine complexity can come into play).

That showing lower bounds for MIP is hard should maybe not be too surprising, because we don't even know how to prove lower bounds for AM protocols.

Answer 3

A section of the Complexity Zoo lists the most important Communication Complexity classes.

Answer 4

The fundamental reason there are such limitations on communication complexity is that there is only ever a linear amount of total information that needs to be communicated (the inputs). Although Hartmut Klauck already essentially pointed this out in his answer, I wanted to highlight an answer to the other OQ regarding the underlying reason for this fundamental limitation, namely, that the players are computationally unbounded.

If one would like to consider "higher" communication classes, a natural thing to look at (instead) is combined communication/computational complexity, which people are definitely aware of and has been studied in various guises, but I think hasn't really been systematically studied. For example, in the study of interactive proofs, it is common to consider the effects of the computational limitations of the players, though not quite as common to consider the total number of bits communicated. The latter is more common in studying PCPs, where e.g. a PCP of poly size requiring $d(n)$ queries only needs $O(d(n)\log n)$ bits to be communicated. When $d(n)=O(1)$, I think the converse is also essentially true, so that query complexity in PCPs is closely related to this issue of combined communication/computational complexity.