We prove that the modular communication complexity of the
undirected graph connectivity problem UCONN equals Theta(n),
in contrast to the well-known Theta(n*log n) bound in the
deterministic case, and to the Omega(n*loglog n) lower bound
in the nondeterministic case, recently proved by ... more >>>

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. ... more >>>