The communication complexity of pointer chasing

Abstract

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. C. Damm, S. Jukna and J. Sgall (1998, Comput. Complexity7, 109-127) showed an upper bound of O(n log^(k−1) n) for this problem. We prove a matching lower bound; this improves the lower bound of ∑(n) shown by N. Nisan and A. Widgerson (1993, SIAM J. Comput.22, 211-219), and yields a corresponding improvement in the hierarchy results derived by them and by H. Klauck (1998, in "Proceeding of the Thirteenth Annual IEEE Conference on Computational Complexity," pp. 141-152) for bounded-depth monotone circuits. We consider the bit version of this problem, and show upper and lower bounds. This implies that there is an abrupt jump in complexity, from linear to superlinear, when the number of rounds is reduced to k/2 or less. We also consider the s-paths version (originally studied by H. Klauck) and show an upper bound. The lower bounds are based on arguments using entropy. One of the main contributions of this work is a transfer lemma for distributions with high entropy; this should be of independent interest.