ECCC-Report TR94-022https://eccc.weizmann.ac.il/report/1994/022Comments and Revisions published for TR94-022en-usMon, 12 Dec 1994 00:00:00 +0200
Paper TR94-022
| The MÃ¶bius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem |
Christoph Meinel,
Stephan Waack
https://eccc.weizmann.ac.il/report/1994/022We 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.
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/022