ECCC-Report TR96-017https://eccc.weizmann.ac.il/report/1996/017Comments and Revisions published for TR96-017en-usMon, 19 Feb 1996 12:29:31 +0200
Paper TR96-017
| The ``Log Rank'' Conjecture for Modular Communication Complexity |
Christoph Meinel,
Stephan Waack
https://eccc.weizmann.ac.il/report/1996/017
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.
Mon, 19 Feb 1996 12:29:31 +0200https://eccc.weizmann.ac.il/report/1996/017