On relations between counting communication complexity classes

摘要

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⩾2. Moreover, non-determinism and modularity are incomparable to a large extend. On the other hand, if m=p1ℓ1·…·prℓr is the prime decomposition of m⩾2, then the complexity classes MODmPcc and MODρ(m)Pcc coincide, where ρ(m)=p1·…·pr.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.