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: Approximation, Randomization, and Combinatorial Optimiza- tion
1 Pith paper cite this work, alongside 3 external citations. Polarity classification is still indexing.
1
Pith paper citing it
3
external citations · OpenAlex
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.