ECCC-Report TR95-034https://eccc.weizmann.ac.il/report/1995/034Comments and Revisions published for TR95-034en-usFri, 30 Jun 1995 16:14:53 +0300
Paper TR95-034
| Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems |
Christoph Meinel,
Stephan Waack
https://eccc.weizmann.ac.il/report/1995/034We 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.
Fri, 30 Jun 1995 16:14:53 +0300https://eccc.weizmann.ac.il/report/1995/034