ECCC-Report TR09-017https://eccc.weizmann.ac.il/report/2009/017Comments and Revisions published for TR09-017en-usFri, 06 Mar 2009 19:34:10 +0200
Paper TR09-017
| The Maximum Communication Complexity of Multi-party Pointer Jumping. |
Joshua Brody
https://eccc.weizmann.ac.il/report/2009/017 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.
Fri, 06 Mar 2009 19:34:10 +0200https://eccc.weizmann.ac.il/report/2009/017