Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

Details Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

2008-02-20

arxiv.org/abs/0802.2843v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Computational Complexity

Scientific paper

We study the one-way number-on-the-forehead (NOF) communication complexity of the $k$-layer pointer jumping problem with $n$ vertices per layer. This classic problem, which has connections to many aspects of complexity theory, has seen a recent burst of research activity, seemingly preparing the ground for an $\Omega(n)$ lower bound, for constant $k$. Our first result is a surprising sublinear -- i.e., $o(n)$ -- upper bound for the problem that holds for $k \ge 3$, dashing hopes for such a lower bound. A closer look at the protocol achieving the upper bound shows that all but one of the players involved are collapsing, i.e., their messages depend only on the composition of the layers ahead of them. We consider protocols for the pointer jumping problem where all players are collapsing. Our second result shows that a strong $n - O(\log n)$ lower bound does hold in this case. Our third result is another upper bound showing that nontrivial protocols for (a non-Boolean version of) pointer jumping are possible even when all players are collapsing. Our lower bound result uses a novel proof technique, different from those of earlier lower bounds that had an information-theoretic flavor. We hope this is useful in further study of the problem.

Affiliated with

Also associated with

No associations

Rating

Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647808