TR95-044 Authors: Carsten Damm, Stasys Jukna, Jiri Sgall

Publication: 18th September 1995 14:48

Downloads: 949

Keywords:

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

blackboard.

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.