ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-022 | 12th December 1994 00:00

The Möbius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint