The communication complexity of pointer chasing
Stephen J. Ponzio, Jaikumar Radhakrishnan, S. Venkatesh · 1999
We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. Damm, Jukna and Sgall [2] showed an upper bound of O(n log(k\\Gamma 1) n) for this problem. We prove a matching lower bound; this improves the lower bound of \\Omega (n) shown by Nisan and Wigderson [11], and yields a corresponding improvement in the hierarchy results derived in [11, 7] 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 Klauck [7]) 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.