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 con…