文章基本信息

标题：Some Bounds on Multiparty Communication Complexity of Pointer Jumping
本地全文：下载
作者：Carsten Damm ; Stasys Jukna ; Jiri Sgall 等
期刊名称：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