__
TR09-017 | 20th February 2009 00:00
__

#### The Maximum Communication Complexity of Multi-party Pointer Jumping.

**Abstract:**
We study the one-way number-on-the-forhead (NOF) communication

complexity of the k-layer pointer jumping problem. Strong lower

bounds for this problem would have important implications in circuit

complexity. All of our results apply to myopic protocols (where

players see only one layer ahead, but can still see arbitrarily far

behind them.) Furthermore, our results apply to the maximum

communication complexity, where a protocol is charged for the

maximum communication sent by a single player rather than the

total communication sent by all players.

Our main result is a lower bound of n/2 bits for deterministic

protocols, independent of the number of players. We also provide a

matching upper bound, as well as an Omega(n/(k log n))

lower bound for randomised protocols, improving on the bounds of

Chakrabarti. In the non-Boolean version of the

problem, we give a lower bound of n(log^{(k-1)} n)(1-o(1)) bits,

essentially matching the upper bound from Damm, Junka, and Sgall.