Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-034 | 30th June 1995 00:00

Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

RSS-Feed

Abstract:

We investigate the probabilistic communication complexity
(more exactly, the majority communication complexity,)
of the graph accessibility problem GAP and
its counting versions MOD_k-GAP, k > 1.
Due to arguments concerning matrix variation ranks
and certain projection reductions, we prove
that, for any partition of the input variables,
GAP and MOD_k-GAP have majority communication complexity
\Omega(n), where n denotes the number of nodes of the
graphs under consideration.



ISSN 1433-8092 | Imprint