期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：multiparty communication complexity, one-way communication, pointer jumping
