Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-014 | 23rd January 2007 00:00

Lower Bounds for Multi-Player Pointer Jumping



We consider the $k$-layer pointer jumping problem in the one-way
multi-party number-on-the-forehead communication model. In this problem,
the input is a layered directed graph with each vertex having outdegree
$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em
except} the $i$th. The players must communicate, in the order
$1,2,\ldots,k$, to determine the vertex reached by following edges from
a special start vertex. This problem has been considered by a number of
researchers in the past because sufficiently strong lower bounds for it
would have major consequences in circuit complexity.

We take an information complexity approach to this problem and obtain
three lower bounds that improve upon earlier work. For myopic protocols
(where players may see only one layer ahead but arbitrarily far behind),
we greatly improve a lower bound due to Gronemeier (2006). Our new
lower bound is $\Omega(n/k)$, where $n$ is the number of vertices per
layer. For conservative protocols (where players may see arbitrarily far
ahead but not behind, instead seeing only the vertex reached by
following the pointers up to their layer), we extend an $\Omega(n/k^2)$
lower bound due to Damm, Jukna and Sgall (1998) so that it applies for
all $k$.

The above two bounds apply even to the Boolean version of pointer
jumping. Our third lower bound is for the non-Boolean case and for
$k\le\log^*n$. We obtain an $\Omega(n\log^{(k-1)}n)$ bound for myopic
protocols. Damm et al.~had obtained a similar bound for deterministic
conservative protocols. All our lower bounds apply directly to
randomised protocols.

ISSN 1433-8092 | Imprint