TR96-017 Authors: Christoph Meinel, Stephan Waack

Publication: 19th February 1996 12:29

Downloads: 3272

Keywords:

The ``log rank'' conjecture consists in the question how exact

the deterministic communication complexity of a problem can be

determinied in terms of algebraic invarants of the communication

matrix of this problem. In the following, 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 obtained bounds for the modular communication complexity

we can conclude exponential lower bounds on the size of depth two

circuits having arbitary symmetric gates at the bottom level

and a MOD_m-gate at the top.