Under the auspices of the Computational Complexity Foundation (CCF)
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 Raz and Spieker.
We obtain our result by combining M"obius function techniques
due to Lovasz and Saxe with rank and projection reduction arguments.