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 ... more >>>

We consider the well known problem of determining the k'th vertex reached by chasing pointers in a directed graph of out-degree 1. The famous "pointer doubling" technique provides an O(log k) parallel time algorithm on a Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that this problem requires Omega(k) steps on an ... more >>>

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$, ... more >>>

In this paper we study the one-way multi-party communication model, in which every party speaks exactly once in its turn. For every fixed $k$, we prove a tight lower bound of $\Omega{n^{1/(k-1)}}$ on the probabilistic communication complexity of pointer jumping in a $k$-layered tree, where the pointers of the $i$-th ... more >>>