Q:

Communication Complexity ...Classes?

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:

 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...
 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?

A:

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

A:

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.

A:

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

