Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-044 | 18th September 1995 00:00

Some Bounds on Multiparty Communication Complexity of Pointer Jumping


Authors: Carsten Damm, Stasys Jukna, Jiri Sgall
Publication: 18th September 1995 14:48
Downloads: 1245


We introduce the model of conservative one-way multiparty complexity
and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered
graph with a starting node and layers of nodes, and a single edge
from each node to one node from the next layer. The output is the
node reached by following edges from the starting node.

In a conservative protocol Player i can see only the node reached by
following the first i-1 edges and the edges on the j-th layer for
each j > i (compared to the general model where he sees edges of all
layers except for the i-th one). In a one-way protocol, each player
communicates only once: first Player 1 writes a message on the
blackboard, then Player 2, etc., until the last player gives the
answer. The cost is the total number of bits written on the

Our main results are the following bounds on k-party conservative
one-way communication complexity of pointer jumping with k layers:

(1) A lower bound of theta(n/k^2) for any k = O(n^{1/3-\epsilon}).
This is the first lower bound on multiparty communication complexity
that works for more than log n players.

(2) Matching upper and lower bounds of theta(n log^{(k-1)}n) for
k \leq \log^* n. No better one-way protocols are known, even if we
consider non-conservative ones.

ISSN 1433-8092 | Imprint