We introduce the model of conservative one-way multiparty complexity and pr
ove lower and upper bounds on the complexity of pointer jumping.
The pointer jumping function takes as its input a directed layered graph wi
th a starting node and Ic layers of n nodes, and a single edge from each no
de to one node from the next layer. The output is the node reached by follo
wing Ic edges from the starting node. In a conservative protocol, the ith p
layer can see only the node reached by following the first i - 1 edges and
the edges on the jth layer for each j > i. This is a restriction of the gen
eral model where the ith player sees edges of all layers except for the ith
one. In a one-way protocol, each player communicates only once in a prescr
ibed order: first Player I writes a message on the blackboard, then Player
2, etc., until the last player gives the answer. The cost is the total numb
er of bits written on the blackboard.
Our main results are the following bounds on k-party conservative one-way c
ommunication complexity of pointer jumping with k layers:
(1) A lower bound of order Omega(n/k(2)) for any k = O(n(1/3-epsilon)).
(2) Matching upper and lower bounds of order Theta(n log((k-1)) n) for k le
ss than or equal to log* n.