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?
Communication Complexity ...Classes?
cc.complexity theory;complexity classes;big picture;communication complexity
It seems that you are looking for this paper: http://portal.acm.org/citation.cfm?id=1382439.1382962