The communication complexity of pointer chasing (Q5943092)

The bounded round two-party communication complexity of a particular problem -- the pointer chasing problem -- is studied. First, a nonlinear lower bound is proved that matches the known upper bound for this problem. Then, the bit version of the problem is considered, and upper and lower bounds are shown. Also, a certain generalization of the pointer chasing problem, the so-called \(s\)-pointer game, is considered and its upper bound obtained.