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.
On total communication complexity of collapsing protocols for pointer jumping problem
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper focuses on bounding the total communication complexity of collapsing protocols for multiparty pointer jumping problem ($MPJ_k^n$). Brody and Chakrabati in \cite{bc08} proved that in such setting one of the players must communicate at least $n - 0.5\log{n}$ bits. Liang in \cite{liang} has shown protocol matching this lower bound on maximum complexity. His protocol, however, was behaving worse than the trivial one in terms of total complexity (number of bits sent by all players). He conjectured that achieving total complexity better then the trivial one is impossible. In this paper we prove this conjecture. Namely, we show that for a collapsing protocol for $MPJ_k^n$, the total communication complexity is at least $n-2$ which closes the gap between lower and upper bound for total complexity of $MPJ_k^n$ in collapsing setting.
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.