With unlimited interaction, k-step pointer chasing still requires Ω(k log(n/k)) randomized communication (or Ω(k log log k) for zero error), so the trivial k-round protocol is near-optimal.
In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC)
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Pointer Chasing with Unlimited Interaction
With unlimited interaction, k-step pointer chasing still requires Ω(k log(n/k)) randomized communication (or Ω(k log log k) for zero error), so the trivial k-round protocol is near-optimal.