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

Joshua Brody & Amit Chakrabarti
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...