Pith. sign in

REVIEW 1 major objections 5 minor 30 references

Pointer Chasing with Unlimited Interaction

T0 review · 1 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that even with unlimited interaction, k-step pointer chasing requires Ω(k log(n/k)) bits for constant-error randomized protocols and Ω(k log log k) bits for zero-error protocols, making the trivial k-round protocol nearly o

desk verdict Novel and mostly sound, but the zero-error theorem has a gap: the proof reduces Cycle_k to a larger step count, so the stated bound for PC_{n,k} does not follow as written. read the letter →

arxiv 2508.19158 v1 pith:Y3X7J74O submitted 2025-08-26 cs.CC

Orr Fischer , Rotem Oshman , Adi Rosen , Tal Roth This is my paper · ORCID
classification cs.CC MSC 68Q1168Q17
keywords pointerchasingcommunicationcomplexityrandomizedlowerboundszero-errorprotocolsroundOR-IndexCycleprobleminteraction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Pointer chasing is the two-player task where Alice and Bob each hold the outgoing edges of one side of a bipartite graph, and must report where a k-step walk from a fixed start ends. The obvious protocol uses one message per step and O(k log n) bits; this paper asks whether allowing unlimited back-and-forth interaction can beat that. It proves that it cannot by much: any randomized protocol with constant nonzero error must send Ω(k log(n/k)) bits in expectation, and any zero-error randomized protocol must send Ω(k log log k) bits in expectation. The result matters because pointer chasing is a standard way to show that some tasks are inherently sequential—more conversation does not replace the step-by-step chase. As a byproduct, the bounds nearly close the gap for protocols restricted to at most k−1 rounds when k is large.

What carries the argument

The constant-error bound runs through a reduction from OR-Index_{r,m}, the disjunction of m instances of the Index problem, to PC^f_{n,k}: a chain of m gadgets, each with one Alice-side vertex and r Bob-side vertices, routes a two-step walk either into the next gadget or into a distinguished accepting vertex, so the walk's endpoint encodes the OR of the m Index answers. The external Ω(m log r) lower bound for OR-Index then becomes Ω(k log(n/k)). The zero-error bound runs through a reduction from Cycle_{k'} to PC^f_{n,2k'}, where k' is the smallest prime above k: the cycle is extended by fresh vertices, and because k' is prime, a 2k'-step walk returns to its start exactly when the matching cy

What would settle it

Give a constant-error randomized protocol for the regime k = Θ(n^{3/4}) that solves PC^f_{n,k} with expected communication o(k log(n/k)) bits; Theorem 3 says this is impossible. For the zero-error claim, exhibit a protocol with expected communication o(k log log k) bits on the same inputs.

Watch

Extended reading notes

Core claim

The paper's central claim is that the trivial k-round protocol for k-step pointer chasing is nearly tight even when the number of rounds is unrestricted. Formally, Theorem 3 states that for any non-trivial output function f, there is a constant error ϵ ∈ (0,1) such that the randomized ϵ-error communication complexity of PC^f_{n,k} is Ω(k log(n/k)); Theorem 4 states that any zero-error randomized protocol must send Ω(k log log k) bits in expectation. Both results hold for the weaker version of the problem in which f is any non-trivial function of the final endpoint. The lower bounds are obtained by two non-communicating reductions: from OR-Index for the constant-error case, and from the Cycle

Load-bearing premise

The main theorem inherits the external lower bound that OR-Index_{r,m} costs Ω(m log r) bits; if that bound were weaker, the Ω(k log(n/k)) result would lose its stated form. Separately, Corollary 1 relies on an unproved assertion in Section 1.1 that prior exactly-round lower bounds can be adapted to at-most-round protocols at a cost of only k bits.

Editorial extensions

If this is right

  • For protocols using at most k−1 rounds, combining this Ω(k log(n/k)) bound with an adapted Ω(n/k) bound gives Ω((n/k) + k log(n/k)) expected communication, nearly matching the O((n/k + k) log n) upper bound in all regimes of k.
  • For k = Θ(n^δ) with 1/2 < δ < 1, the log n factor in the earlier upper bound is necessary for constant-error protocols, answering a recent conjecture.
  • Because the lower bounds hold with no round restriction, they automatically apply to any protocol with at most t rounds for any t, including the previously studied exactly-(k−1)-round and Bob-first settings.
  • The zero-error bound shows that Las Vegas protocols also need roughly k log log k expected bits, though the gap between this and the trivial O(k log n) remains open in the zero-error regime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The gadget-chain reduction is more general than pointer chasing: any problem expressible as a sequential evaluation of m independent queries, where one player selects coordinates and the other's answers route to the next query, should inherit a similar Ω(m log r) lower bound.
  • The prime-extension step suggests a template for transferring cycle-length divisibility facts into walk problems; applying sharper number-theoretic facts about cycle lengths could strengthen the zero-error bound.
  • A natural next question the paper leaves open is whether zero-error protocols can be forced to pay the same Ω(k log(n/k)) as constant-error protocols, or whether the log log k gap is real.
  • The exactly-rounds versus at-most-rounds distinction used here may affect other communication lower bounds whose proofs assume a fixed last message; unlimited-round lower bounds are a cleaner way to state hardness of sequential tasks.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper studies the two-party communication complexity of k-step pointer chasing when the number of communication rounds is unrestricted. It proves two lower bounds: for randomized protocols with constant error, an Ω(k log(n/k)) lower bound via a reduction from OR-Index; and for zero-error randomized protocols, an Ω(k log log k) lower bound via a reduction from Cycle. The authors also derive consequences for protocols restricted to at most k−1 rounds, claiming near-tight bounds in some regimes. The trivial k-round O(k log n)-bit protocol is shown to be nearly optimal even with unlimited interaction, if the main theorems hold.

Significance. If the main results hold, they are significant: they settle an interesting open question for the unrestricted-round setting, close a gap for at-most-(k−1)-round protocols when k≫√n, and refute a recent conjecture about the log n factor for k=n^δ. The reductions are simple and elegant, and the paper makes good use of external lower bounds (Pătrașcu for OR-Index; Raz–Spieker for Cycle). The paper is not self-citing or circular. However, one of the two central proof steps — the zero-error lower bound — contains a parameter mismatch that is currently unresolved and requires a nontrivial repair.

major comments (1)
  1. [§3.2, Theorem 4] The proof reduces Cycle_k to PC^f_{n,2k'} for a prime k' with k < k' ≤ 2k, and then states that Theorem 4 'immediately follows.' This is not valid as written: the reduction establishes a lower bound for pointer chasing with 2k' steps, not for the k-step problem claimed in Theorem 4. A lower bound for a larger number of steps does not automatically transfer to a smaller number of steps, since the k-step problem may be easier. No monotonicity or padding lemma is supplied. To repair, the authors should either prove an explicit padding reduction showing that PC^f_{n,k} is at least as hard as PC^f_{n,2p} for every prime p with 2p ≤ k (using the slack n ≥ 4k to insert k−2p dummy steps and then applying Bertrand's postulate to get p=Θ(k)), or weaken the theorem's statement to the class of step counts that are twice a prime. As written, the claimed Ω(k log log k) lower bound for arbitrary k is n
minor comments (5)
  1. [§3.1, final paragraph] 'Taking r = Θ(n/k) and m = Θ(n)' should read 'm = Θ(k)'. The text has already set k = Θ(m), and the reduction requires n = Θ(rm); as written the parameter choices are inconsistent.
  2. [§3.1, Corollary 3 proof] 'Since r ≤ k' is not a stated or implied condition and is generally false (e.g., k < √n). The intended argument is that the walk reaches vdisj at step 2m and then stays there because 2m ≤ k and vdisj is a fixed point. Please correct the justification.
  3. [§3.2, Cycle_k to Cycle_k' reduction] In the definition of W′, '{u1,...,un}' should be '{w1,...,wk}'. Also, the phrase 'increasing the length of the cycle by 2(k′−k)−1 edges' in the preceding overview is confusing: the net increase is 2(k′−k), since one original edge is removed.
  4. [§1.1, Corollary 1] The assertion that the lower bounds of [15] and [19] can be adapted to protocols with at most k−1 rounds at a cost of k bits is not proved or accompanied by a reference. If Corollary 1 is meant as a formal contribution, this adaptation should be supplied or at least sketched; otherwise the informal claim should be flagged as a conjecture.
  5. [§3.2, Observation 1] The proof that one may assume f(1)=0 and f(i)=1 for 2≤i≤2k is phrased as 'using a single extra step', which is unclear. A vertex relabeling (sending a zero-valued index to label 1 and mapping 2k one-valued indices to labels 2..2k+1) suffices when n≥4k; please rewrite the argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: reductions from external OR-Index and Cycle lower bounds; only caveat is a correctness gap in Theorem 4's step-count parameter, not circularity.

full rationale

The paper's central lower bounds are obtained by reductions from OR-Index (Lemma 1, due to Pătrașcu [24]) and Cycle (Lemma 2, due to Raz–Spieker [27]). These are external, published lower bounds with no parameter fitted to pointer chasing; the gadget constructions are explicit and the correctness proofs reduce the target value to OR-Index / Cycle. No equation in the paper defines one result in terms of the other; no fitted input is relabeled as a prediction; and the authors do not cite their own prior work as load-bearing. The near-tightness comparison uses the independent Nisan–Wigderson protocol [22]. The only significant caveat is not circular: the proof of Theorem 4 reduces Cycle_k to PC^f_{n,2k'} with k < k' ≤ 2k, so the stated Ω(k log log k) bound for PC^f_{n,k} does not follow as written (a lower bound for a larger step count does not transfer to a smaller one). This is a correctness/parameterization gap, not a reduction that is equivalent to its inputs by construction. The Section 1.1 claim that [15,19] can be adapted at cost k bits is an unproved assertion about external work, but it is not a self-citation and is not used in the two main theorems. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's results rest on two external lower-bound lemmas (OR-Index from Patrascu; Cycle_n from Raz-Spieker), the standard nondeterministic-to-zero-error translation, and Bertrand's postulate. No free parameters are fitted and no entities are invented.

assumptions (5)
  • standard math Randomized public-coin communication complexity of OR-Index_{r,m} with error 1/9999 is Ω(m log r) (Lemma 1, citing Patrascu [24]).
    Load-bearing external theorem used to derive the main Ω(k log(n/k)) lower bound in Theorem 3.
  • standard math Nondeterministic communication complexity of Cycle_n is Ω(n log log n), and nondeterministic complexity lower-bounds zero-error randomized complexity (Lemma 2, citing Raz-Spieker [27] and [17] Prop 3.7).
    Used in Theorem 4 to obtain the Ω(k log log k) zero-error bound.
  • standard math There exists a prime k' with k < k' ≤ 2k (Bertrand's postulate), used implicitly to pick the prime number of steps in the zero-error reduction.
    The primality of k' is essential for Lemma 5: a 2k'-walk returns to u1 iff the cycle is Hamiltonian.
  • domain assumption Observation 1: WLOG f can be relabeled so that f(1)=0 and f(i)=1 for all 2 ≤ i ≤ 2k, given f non-trivial and n ≥ 4k.
    This normalization is needed in the Cycle-to-PC reduction so the output distinguishes return-to-1 from elsewhere; it uses majority relabeling and n ≥ 4k to guarantee enough indices.
  • domain assumption The external lower bounds are stated for the same model as the paper's preliminaries: randomized public-coin, expected communication, worst-case over inputs.
    The paper's complexity measure is expected communication; Lemmas 1 and 2 are assumed to match this model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pointer Chasing with Unlimited Interaction." pith.science (2026). https://pith.science/paper/Y3X7J74O

@misc{pith2026250819158,
  author       = {Pith},
  title        = {Pith review of: Pointer Chasing with Unlimited Interaction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y3X7J74O}},
  note         = {Machine review of arXiv:2508.19158}
}
abstract

Pointer-chasing is a central problem in two-party communication complexity: given input size $n$ and a parameter $k$, the two players Alice and Bob are given functions $N_A, N_B: [n] \rightarrow [n]$, respectively, and their goal is to compute the value of $p_k$, where $p_0 = 1$, $p_1 = N_A(p_0)$, $p_2 = N_B(p_1) = N_B(N_A(p_0))$, $p_3 = N_A(p_2) = N_A(N_B(N_A(p_0)))$ and so on, applying $N_A$ in even steps and $N_B$ in odd steps, for a total of $k$ steps. It is trivial to solve the problem using $k$ communication rounds, with Alice speaking first, by simply ``chasing the function'' for $k$ steps. Many works have studied the communication complexity of pointer chasing, although the focus has always been on protocols with $k-1$ communication rounds, or with $k$ rounds where Bob (the ``wrong player'') speaks first. Many works have studied this setting giving sometimes tight or near-tight results. In this paper we study the communication complexity of the pointer chasing problem when the interaction between the two players is unlimited, i.e., without any restriction on the number of rounds. Perhaps surprisingly, this question was not studied before, to the best of our knowledge. Our main result is that the trivial $k$-round protocol is nearly tight (even) when the number of rounds is not restricted: we give a lower bound of $\Omega(k \log (n/k))$ on the randomized communication complexity of the pointer chasing problem with unlimited interaction, and a somewhat stronger lower bound of $\Omega(k \log \log{k})$ for protocols with zero error. When combined with prior work, our results also give a nearly-tight bound on the communication complexity of protocols using at most $k-1$ rounds, across all regimes of $k$; for $k > \sqrt{n}$ there was previously a significant gap between the upper and lower bound.

Figures

Figures reproduced from arXiv: 2508.19158 by the authors.

Figure 1
Figure 1. The left vertex and xi-th right vertex of the gadget for coordinate i ∈ [m], together with the left vertex of the gadget for coordinate i + 1, and vint vertices. Each gadget has one left vertex and r right vertices. The left vertex of the gadget for coordinate i is connected to the xi-the right vertex. For any j ∈ [r], the j-th right vertex of the gadget for coordinate i is connected to the vint vertex if (yi) j = 1… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 26 canonical work pages

  1. [1]

    In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC

    Assadi, S., Chen, Y., Khanna, S.: Polynomial pass lower bounds for graph streaming algorithms. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC. pp. 265–276 (2019). https://doi.org/10.1145/3313276.3316361

    arXiv 2019

  2. [2]

    In: Proceedings of the 24th Annual IEEE Conference on Computational Com- plexity, CCC

    Brody, J.: The maximum communication complexity of multi-party pointer jump- ing. In: Proceedings of the 24th Annual IEEE Conference on Computational Com- plexity, CCC. pp. 379–386 (2009). https://doi.org/10.1109/CCC.2009.30

    work page doi:10.1109/ccc.2009.30 2009

  3. [3]

    In: STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science

    Brody, J., Chakrabarti, A.: Sublinear communication protocols for multi-party pointer jumping and a related lower bound. In: STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science. pp. 145–156 (2008). https://doi.org/10.4230/LIPIcs.STACS.2008.1341

    work page arXiv 2008

  4. [4]

    In: Approximation, Randomization, and Combinatorial Optimiza- tion

    Brody, J., Sanchez, M.: Dependent random graphs and multi-party pointer jumping. In: Approximation, Randomization, and Combinatorial Optimiza- tion. Algorithms and Techniques, APPROX/RANDOM. pp. 606–624 (2015). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.606

    work page doi:10.4230/lipics.approx-random.2015.606 2015

  5. [5]

    In: 22nd An- nual IEEE Conference on Computational Complexity (CCC)

    Chakrabarti, A.: Lower bounds for multi-player pointer jumping. In: 22nd An- nual IEEE Conference on Computational Complexity (CCC). pp. 33–45 (2007). https://doi.org/10.1109/CCC.2007.14

    work page doi:10.1109/ccc.2007.14 2007

  6. [6]

    Damm, C., Jukna, S., Sgall, J.: Some bounds on multiparty communication com- plexity of pointer jumping. Comput. Complex.7(2), 109–127 (1998)

    work page 1998

  7. [7]

    In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC)

    Duris, P., Galil, Z., Schnitger, G.: Lower bounds on communication complexity. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC). pp. 81–91. ACM (1984). https://doi.org/10.1145/800057.808668

    work page arXiv 1984

  8. [8]

    Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph dis- tances in the data-stream model. SIAM J. Comput. 38(5), 1709–1727 (2008). https://doi.org/10.1137/070683155

    work page doi:10.1137/070683155 2008

Show all 30 references
  1. [9]

    In: Mathematical Foundations of Computer Science

    Gronemeier, A.: Nof-multiparty information complexity bounds for pointer jump- ing. In: Mathematical Foundations of Computer Science. pp. 459–470 (2006). https://doi.org/10.1007/11821069\_40

    2006 doi

  2. [10]

    In: Proceedings of the 28th Conference on Computational Complexity, CCC

    Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph process- ing. In: Proceedings of the 28th Conference on Computational Complexity, CCC. pp. 287–298 (2013). https://doi.org/10.1109/CCC.2013.37 Pointer Chasing with Unlimited Interaction 15

    2013 doi

  3. [11]

    In: Proceedings of the Nineteenth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA

    Harvey, N.J.A.: Matroid intersection, pointer chasing, and young’s seminormal representation of Sn. In: Proceedings of the Nineteenth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA. pp. 542–549 (2008)

    2008

  4. [12]

    In: 43rd Symposium on Foundations of Computer Science FOCS

    Jain, R., Radhakrishnan, J., Sen, P.: Privacy and interaction in quantum communi- cation complexity and a theorem about the relative entropy of quantum states. In: 43rd Symposium on Foundations of Computer Science FOCS. pp. 429–438 (2002). https://doi.org/10.1109/SFCS.2002.1181967

    2002 arXiv

  5. [13]

    In: FST TCS Foundations of Software Technology and Theoretical Computer Science

    Jain, R., Radhakrishnan, J., Sen, P.: The quantum communication complex- ity of the pointer chasing problem: The bit version. In: FST TCS Foundations of Software Technology and Theoretical Computer Science. pp. 218–229 (2002). https://doi.org/10.1007/3-540-36206-1\_20

    2002 doi

  6. [14]

    CoRR abs/1405.7596 (2014), http://arxiv.org/abs/1405.7596

    Jastrzebski, M.: On total communication complexity of collapsing pro- tocols for pointer jumping problem. CoRR abs/1405.7596 (2014), http://arxiv.org/abs/1405.7596

    2014 arXiv

  7. [15]

    In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing

    Klauck, H.: On quantum and probabilistic communication: Las vegas and one- way protocols. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. pp. 644–651 (2000). https://doi.org/10.1145/335305.335396

    2000

  8. [16]

    In: Vitter, J.S., Spirakis, P.G., Yannakakis, M

    Klauck, H., Nayak, A., Ta-Shma, A., Zuckerman, D.: Interaction in quantum com- munication and the complexity of set disjointness. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing. pp. 124–133. ACM (2001). h...

    2001

  9. [17]

    Kushilevitz,E.,Nisan,N.:Communicationcomplexity.CambridgeUniversityPress (1997)

    1997

  10. [18]

    Theory Comput

    Liang, H.: Optimal collapsing protocol for multiparty pointer jumping. Theory Comput. Syst. 54(1), 13–23 (2014). https://doi.org/10.1007/s00224-013-9476-x, https://doi.org/10.1007/s00224-013-9476-x

    2014 doi

  11. [19]

    In: 16th Innovations in Theoretical Computer Science Conference, ITCS

    Mao, X., Yang, G., Zhang, J.: Gadgetless lifting beats round elimination: Im- proved lower bounds for pointer chasing. In: 16th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 325, pp. 75:1–75:14 (2025). https://doi.org/10.4230/LIPICS.ITCS.2025.75

    2025 doi

  12. [20]

    Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asym- metric communication complexity. J. Comput. Syst. Sci. 57(1), 37–49 (1998). https://doi.org/10.1006/JCSS.1998.1577

    1998

  13. [21]

    In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC

    Nanongkai, D., Sarma, A.D., Pandurangan, G.: A tight unconditional lower bound on distributed randomwalk computation. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC. pp. 257–266 (2011). https://doi.org/10.1145/1993806.1993853

    2011

  14. [22]

    Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. SIAM J. Comput. 22(1), 211–219 (1993)

    1993

  15. [23]

    Papadimitriou, C.H., Sipser, M.: Communication complexity. J. Comput. Syst. Sci. 28(2), 260–269 (1984). https://doi.org/10.1016/0022-0000(84)90069-2

    1984 doi

  16. [24]

    Patrascu, M.: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput. 40(3), 827–847 (2011). https://doi.org/10.1137/09075336X

    2011 doi

  17. [25]

    In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing

    Ponzio, S., Radhakrishnan, J., Venkatesh, S.: The communication complexity of pointer chasing: Applications of entropy and sampling. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing. pp. 602–611 (1999). https://doi.org/10.1145/301250.301413

    1999

  18. [26]

    Cam- bridge University Press (2020)

    Rao, A., Yehudayoff, A.: Communication Complexity, and Applications. Cam- bridge University Press (2020)

    2020

  19. [27]

    log rank

    Raz, R., Spieker, B.: On the "log rank"-conjecture in communication complexity. Comb. 15(4), 567–588 (1995) 16 O. Fischer et al

    1995

  20. [28]

    Sen, P., Venkatesh, S.: Lower bounds for predecessor searching in the cell probe model. J. Comput. Syst. Sci. 74(3), 364–385 (2008). https://doi.org/10.1016/J.JCSS.2007.06.016

    2008 doi

  21. [29]

    Viola, E., Wigderson, A.: One-way multiparty communication lower bound for pointer jumping with applications. Comb. pp. 719–743 (2009). https://doi.org/10.1007/s00493-009-2667-z

    2009 doi

  22. [30]

    Yehudayoff,A.:Pointerchasingviatriangulardiscrimination.Comb.Probab.Com- put. pp. 485–494 (2020). https://doi.org/10.1017/S0963548320000085

    2020 doi

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.