ECCC-Report TR95-044https://eccc.weizmann.ac.il/report/1995/044Comments and Revisions published for TR95-044en-usMon, 18 Sep 1995 14:48:02 +0200
Paper TR95-044
| Some Bounds on Multiparty Communication Complexity of Pointer Jumping |
Carsten Damm,
Stasys Jukna,
Jiri Sgall
https://eccc.weizmann.ac.il/report/1995/044We 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.
Mon, 18 Sep 1995 14:48:02 +0200https://eccc.weizmann.ac.il/report/1995/044