Browsing by Author "Meinel, C."

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.

The "log rank" conjecture involves the question of how precisely the deterministic communication complexity of a problem can be described in terms of algebraic invariants of the communication matrix of this problem. We answer this question in the context of modular communication complexity. We show that the modular communication complexity can be exactly characterised in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to exactly determine the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the bounds obtained for the modular communication complexity we deduce exponential lower bounds on the size of depth-two circuits having arbitrary symmetric gates at the bottom level and a MODm-gate at the top.