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

Abstract

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.