Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-017 | 20th February 2009 00:00

The Maximum Communication Complexity of Multi-party Pointer Jumping.


Authors: Joshua Brody
Publication: 6th March 2009 19:34
Downloads: 3013


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.

ISSN 1433-8092 | Imprint