{"id":"29d8d440-cba1-494c-a9c9-626d738896d1","arxiv_id":"2508.19158","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"The paper proves that k-step pointer chasing needs Ω(k log(n/k)) bits of communication even when players may interact for as many rounds as they like, and Ω(k log log k) bits for zero-error protocols. This shows the trivial k-round protocol is essentially optimal, settles a previously open setting, and refutes a recent conjecture.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's proof reduces Cycle_k to PC_{n,2k'} with 2k' > k, so the stated Ω(k log log k) lower bound for PC_{n,k} does not follow as written.","rationale":"The paper's central claim is that the trivial k-round protocol is nearly optimal even with unlimited interaction. Theorem 3 (constant error) appears sound modulo the external OR-Index lower bound, which is a known result and not the weakest point. The zero-error Theorem 4, however, has an internal parameter mismatch. The proof reduces Cycle_k to PC^f_{n,2k'} with k' prime between k and 2k, so the constructed pointer-chasing instance has 2k' ≥ 2k steps. The theorem statement is about PC^f_{n,k} with k steps. A lower bound for a larger step count does not imply a lower bound for a smaller step count unless one has a reduction showing PC^f_{n,k} is at least as hard as PC^f_{n,2k'}. The paper neither states nor proves such a monotonicity/padding reduction, and the natural direction is that fewer steps are easier, not harder. Therefore, as written, the proof of Theorem 4 is incomplete for most values of k. This is not a matter of an external bound being weak; it is an internal logical gap. The reader's weakest_assumption focuses on Lemma 1 and the Corollary 1 adaptation, but I believe the step-count mismatch is more load-bearing because it affects the main zero-error theorem directly. The bound may be true and fixable, but it needs to be demonstrated. The verdict remains CONDITIONAL: the paper should be accepted only after the authors supply a correct proof of Theorem 4 for arbitrary k.","tokens_in":12330,"tokens_out":40730,"duration_ms":363941,"concrete_test":"Instantiate the reduction in §3.2 for a k that is not twice a prime, e.g., k = 6. Attempt to reduce Cycle_{k0} (k0 = Θ(k)) to PC^f_{n,6} by first extending to a prime k' and then padding the 2k'-step walk to exactly 6 steps. Check whether the padding can be implemented by Alice and Bob locally with no extra communication and while preserving the output f-value for the normalized f from Observation 1. If no such padding exists, Theorem 4's proof does not establish the stated bound for k=6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.2, the proof of Theorem 4 reduces Cycle_k to PC^f_{n,2k'} for a prime k' with k < k' ≤ 2k (first paragraph of §3.2). This gives a lower bound for a pointer-chasing instance with 2k' steps. Theorem 4 claims an Ω(k log log k) lower bound for PC^f_{n,k} with k steps. Since 2k' ≥ 2k, the reduction targets strictly more steps than the theorem's parameter. The paper does not provide a reduction showing PC^f_{n,k} is at least as hard as PC^f_{n,2k'}; a lower bound for a larger step count does not automatically transfer to a smaller one, because fewer steps could be easier. Thus, as written, Theorem 4 is only established for step counts that are twice a prime, not for arbitrary k. This is a load-bearing internal gap in one of the paper's two main results.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12566,"tokens_out":26197,"duration_ms":243971,"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":[{"comment":"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","section":"§3.2, Theorem 4"}],"minor_comments":[{"comment":"'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.","section":"§3.1, final paragraph"},{"comment":"'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.","section":"§3.1, Corollary 3 proof"},{"comment":"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.","section":"§3.2, Cycle_k to Cycle_k' reduction"},{"comment":"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.","section":"§1.1, Corollary 1"},{"comment":"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.","section":"§3.2, Observation 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is well-written and the OR-Index reduction (Theorem 3) appears sound. The main issue is the zero-error theorem: the reduction produces a lower bound for PC with 2k' steps, not k steps, and the missing padding argument is not a one-line fix because label space and the parity of the dummy steps need care. I believe the result is likely true and repairable, but as submitted the central claim of Theorem 4 is not fully proved. The unproved adaptation of [15,19] for Corollary 1 should also be addressed, possibly by moving it to informal discussion."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper opens a genuinely new regime: pointer chasing with unlimited interaction. That question is natural, previously unstudied, and the main constant-error result (Theorem 3) is solid. The OR-Index reduction is clean, the parameter balance n = Θ(rm), k = Θ(m) works, and the Ω(k log(n/k)) lower bound nearly matches the trivial protocol. The byproduct refuting a 2025 conjecture is a nice win. The exposition is mostly clear and the related-work tables are useful.\n\nThe soft spot is Theorem 4. As written, the proof reduces Cycle_k to PC^f_{n,2k'} for a prime k' with k < k' ≤ 2k, so it establishes a lower bound for a pointer-chasing instance with 2k' ≥ 2k steps, not for k steps. That is not a harmless change: a protocol for PC_{n,k} does not automatically solve PC_{n,2k'}. In the Cycle reduction the walk stays on a cycle, so the k-step output depends on k mod cycle length, and you cannot pad the step count without changing the problem. The theorem as stated is therefore not proven. The gap is patchable in principle (e.g., by choosing the prime so that 2k' equals the target k for infinitely many k, or by a more careful gadget), but the present text does not do it.\n\nTwo lesser issues. First, Section 1.1 asserts without proof that the lower bounds of [15,19] can be adapted to 'at most k−1 rounds' at a cost of k bits; this underpins Corollary 1 and needs a reference or a short argument. Second, there are typos, including 'm = Θ(n)' where m = Θ(k) is meant, and a truncated sentence. Minor, but they should be fixed.\n\nThe paper is worth a serious referee: the main question is real, the constant-error result is a genuine advance, and the zero-error gap is a specific technical oversight rather than a sign of carelessness. I would send to peer review, but with a clear request to fix Theorem 4 or restate it to match the proof, and to tighten the at-most-round claim in Section 1.1.","headline":"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.","tokens_in":13057,"tokens_out":7241,"would_cite":true,"duration_ms":64336,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q11","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["pointer chasing","communication complexity","randomized lower bounds","zero-error protocols","round complexity","OR-Index","Cycle problem","interaction"],"falsifier":"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.","tokens_in":12228,"feed_emoji":"🔗","tokens_out":9472,"duration_ms":89405,"temperature":0.7,"pith_summary":"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.","feed_headline":"Ω(k log(n/k)) bits needed even with unlimited rounds","feed_subtitle":"The paper proves the trivial k-round protocol is near-optimal: extra messages barely cut the bits needed.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the lower bound that OR-Index_{r,m} requires Ω(m log r) randomized communication, which the gadget reduction converts into the main Ω(k log(n/k)) bound.","marker":"[24]"},{"why":"Defines the Cycle problem and proves its nondeterministic complexity is Ω(n log log n), the source of the zero-error Ω(k log log k) bound.","marker":"[27]"},{"why":"Gives the O((n/k + k) log n) randomized upper bound for (k−1)-round pointer chasing that the paper's lower bounds nearly match, and the comparison target for the conjectured log n factor.","marker":"[22]"},{"why":"Provides the prior state-of-the-art exactly-round lower bound and the conjecture about the log n factor that Theorem 3 refutes for k = Θ(n^δ).","marker":"[19]"},{"why":"Together with [19], supplies the exactly-round lower bound whose at-most-round adaptation at a cost of k bits is used in Corollary 1.","marker":"[15]"},{"why":"Standard reference for the implication that nondeterministic communication lower bounds imply zero-error randomized lower bounds, used to derive Lemma 2 from the Cycle result.","marker":"[17]"}],"fun_headline_variants":["Unlimited rounds can't beat trivial pointer chasing","Pointer chasing needs Ω(k log(n/k)) bits even with free chat","Even unlimited interaction keeps pointer chase hard","Extra rounds don't cut pointer-chasing bits","Zero-error needs Ω(k log log k) bits, unlimited rounds"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Unlimited rounds can't beat trivial pointer chasing","Pointer chasing needs Ω(k log(n/k)) bits even with free chat","Even unlimited interaction keeps pointer chase hard","Extra rounds don't cut pointer-chasing bits","Zero-error needs Ω(k log log k) bits, unlimited rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000217,"raw_usage":{"total_tokens":1375,"prompt_tokens":952,"completion_tokens":423,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":345}},"tokens_in":696,"tokens_out":423,"duration_ms":4584,"temperature":1.0,"reasoning_tokens":345,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:58:20.210546+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"log rank","cited_arxiv_id":null,"evidence_quote":"Defines the Cycle problem and proves its nondeterministic complexity is Ω(n log log n), the source of the zero-error Ω(k log log k) bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the O((n/k + k) log n) randomized upper bound for (k−1)-round pointer chasing that the paper's lower bounds nearly match, and the comparison target for the conjectured log n factor."},{"cited_title":"In: 16th Innovations in Theoretical Computer Science Conference, ITCS","cited_arxiv_id":null,"evidence_quote":"Provides the prior state-of-the-art exactly-round lower bound and the conjecture about the log n factor that Theorem 3 refutes for k = Θ(n^δ)."},{"cited_title":"In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing","cited_arxiv_id":null,"evidence_quote":"Together with [19], supplies the exactly-round lower bound whose at-most-round adaptation at a cost of k bits is used in Corollary 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Standard reference for the implication that nondeterministic communication lower bounds imply zero-error randomized lower bounds, used to derive Lemma 2 from the Cycle result."}],"review_version":1}