On relations between counting communication complexity classes

Abstract

We develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established. This extends the investigation of the complexity of communication between two processors in terms of complexity classes initiated by Babai et al. (Proceedings of the 27th IEEE FOCS, 1986, pp. 337-347) and continued in several papers (e.g., J. Comput. System Sci. 41 (1990) 402; 49 (1994) 247; Proceedings of the 36th IEEE FOCS, 1995, pp. 6-15). In particular, it will be shown that for all pairs of distinct primes p and q the communication complexity classes MODpPcc and MODqPcc are incomparable with regard to inclusion. The same is true for PPcc and MODmPcc, for any number m greater than or equal to 2. Moreover, non-determinism and modularity are incomparable to a large extend. On the other hand, if m = p(1)(l1.)...(.)p(r)(lr) is the prime decomposition of m greater than or equal to 2, then the complexity classes MODmPcc and MODrho(m)Pcc coincide, where rho(m) = p(1) (.)...(.) p(r). The results are obtained by characterizing the modular and probabilistic communication complexity in terms of the minimum rank of matrices ranging over certain equivalence classes. Methods from algebra and analytic geometry are used. This paper is the completely revised and strongly extended version of the conference paper Damm et al. (Proc. 9th Ann. STACS, pp. 281-291) where a subset of the results was presented. (C) 2004 Elsevier Inc. All rights reserved.