Paper Info
Title
Optimal Collapsing Protocol for Multiparty Pointer Jumping
Abstract
In this paper, we study the pointer jumping problem under the one-way number-on-the-forehead (NOF) multiparty communication model. This problem is widely considered to be a candidate for proving strong lower bounds under the NOF model, and has applications to proving lower bounds for many other problems.We investigate the maximum communication complexity of collapsing protocols for pointer jumping, where each player sees all layers behind her and only the composition of layers ahead of her. We present a collapsing protocol in which every player communicates at most $n-\frac{1}{2}\log_{2} n+1$ bits, which tightly matches the lower bound of $n-\frac{1}{2}\log_{2} n-2$ given by Brody and Chakrabarti (in Proc. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 145---156, 2008). Actually, in our protocol only three players need to communicate information: the first player sends log2(n+1) bits, the second to last player sends $n-\frac{1}{2}\log_{2} n+1$ bits, and the last player just outputs the answer. A natural question is whether the log2(n+1) bits communicated by the first player is necessary for achieving a low maximum communication complexity. We make progress towards this question by proving that in any collapsing protocol for the 3-player pointer jumping problem, if the first player only sends one bit, then the second player must communicate at least n驴2 bits.
Year
DOI
Venue
2014
10.1007/s00224-013-9476-x
Theory Comput. Syst.
Keywords
Field
DocType
Multiparty communication complexity,Pointer jumping,Number-on-the-forehead model,Collapsing protocol,Total influence
Discrete mathematics,Combinatorics,Upper and lower bounds,Computer science,Pointer jumping,Communication complexity,Models of communication
Journal
Volume
Issue
ISSN
54
1
1432-4350
Citations 
PageRank 
References 
0
0.34
22
Authors
1
Name
Order
Citations
PageRank
Hongyu Liang18416.39