Logo image
Back
Optimal Collapsing Protocol for Multiparty Pointer Jumping
Journal article   Peer reviewed

Optimal Collapsing Protocol for Multiparty Pointer Jumping

Hongyu Liang and Hualou Liang
Theory of computing systems, v 54(1), pp 13-23
2014
DOI: https://doi.org/10.1007/s00224-013-9476-x

Abstract

Article Computer Science Theory of Computation
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 bits, which tightly matches the lower bound of 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 log 2 ( n +1) bits, the second to last player sends bits, and the last player just outputs the answer. A natural question is whether the log 2 ( 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.

Metrics

4 Record Views
2 citations in Web of Science
2 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Computer Science, Theory & Methods
Mathematics
Logo image