{"id":"ed8dffd3-0231-43ab-8af3-d978e1305f2a","arxiv_id":"2507.19859","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims a new tradeoff for 2-approximate all-pairs shortest paths, but the proof has a critical gap in the sampling-based base case.","lead":"A randomized algorithm claims 2-approximate shortest paths for vertex pairs only O(log k) apart in eO(n^{2+1/k}) time, improving a 25-year-old tradeoff. A key probabilistic step in the base case is not justified, and the runtime derivation contains an arithmetic error.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Base case of Section 6.1 samples B_l at rate 2^{-l}; for deg(p)=2^l the probability that B_l contains no neighbor of p is about e^{-1}, a constant rather than 1/n^c, so the claimed high-probability guarantee for the induction anchor fails.","rationale":"The reader's weakest assumption is correct and is the most load-bearing issue in the paper. The base case in Section 6.1 is the only place where the induction for Lemma 6.1 gets started, and it relies on a probabilistic event whose failure probability is a positive constant, not an inverse polynomial. This is not a matter of disagreement with existing consensus; it is an internal probabilistic error in the proof. The section even provides the sampling probability 1/2^l and the degree range [2^l, 2^{l+1}), so the calculation is immediate. I also checked the runtime derivation in Section 8 that the reader flagged as algebraically wrong. With i = log log n - log k - 1, the exponent 2^{i+1} equals (log n)/k, so the term 2^{2^{i+1}} becomes 2^{(log n)/k} = n^{1/k}, giving eO(n^{2+1/k}). That part appears correct; I do not share that secondary objection. The sampling issue, however, is decisive for the proof as written. It may be patchable by sampling B_l with an extra poly-log factor, since the base-case runtime would still be eO(n^2), but the current manuscript does not contain that fix, and the theorem is therefore not established.","tokens_in":21785,"tokens_out":6213,"duration_ms":76287,"concrete_test":"Compute the exact failure probability for the base-case sampling event in a star graph centered at p with n = 2^L leaves, taking l = L and deg(p) = 2^L. The probability that B_l contains no neighbor of p is (1 - 2^{-L})^{2^L}. For L = 20 this is approximately 0.3679, which is far above the required 1/poly(n) bound. This direct evaluation settles that the claimed 'with high probability' event in Section 6.1 is false as stated.","verdict_should_be":"REJECT","load_bearing_attack":"In the base case of Algorithm 5 (Section 6.1), correctness requires that, with high probability, the random set B_l contains a neighbor of the highest-degree vertex p on the st path, where deg(p) in [2^l, 2^{l+1}). The paper states: 'With a high probability, there is a vertex, say w in B_l adjacent to p.' This is not supported. Since each vertex is independently sampled into B_l with probability 1/2^l, the probability that a fixed neighbor of p is sampled is 1/2^l, and the probability that no neighbor of p is sampled is (1 - 1/2^l)^{deg(p)}. When deg(p) = 2^l, this is (1 - 2^{-l})^{2^l} ≈ e^{-1} ≈ 0.37. Even when deg(p) is close to 2^{l+1}, the failure probability is only about e^{-2} ≈ 0.135. This is a constant, not the n^{-c} required by the paper's definition of 'with high probability.' Moreover, the event must hold for all relevant vertex pairs simultaneously; with only constant per-pair success probability, a union bound over n^2 pairs cannot yield high probability. Because this base case is the anchor of the induction proving Lemma 6.1, and Lemma 6.1 directly yields Theorem 1.2 for k = log n, the central correctness argument is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a randomized combinatorial algorithm for 2-approximate all-pairs shortest paths in undirected unweighted graphs, running in eO(n^{2+1/k}) time for all vertex pairs at distance at least O(log k), with k = log n giving eO(n^2) time for pairs at distance at least O(log log n). The approach combines nested vertex sampling and pivot balls, a precomputed (2,1)-approximation as a black box, an ENSURE CLOSENESS preprocessing routine, and an induction whose base case samples random neighbor sets B_l at rate 1/2^l for high-degree vertices. The main theorem for k = log n is Lemma 6.1; Section 8 extends it to general k.","tokens_in":22057,"tokens_out":22880,"duration_ms":247317,"significance":"If correct, this would be the first improvement since Dor-Halperin-Zwick on multiplicative 2-approximation for close pairs, and the near-quadratic result for distance O(log log n) is a clean and appealing statement. The paper is well structured and avoids parameter fitting: the core induction does not depend on self-cited claims, and the use of known (2,1)-approximate APSP as a black box is legitimate. However, the correctness of the entire induction rests on a probabilistic base case that is currently unjustified, as detailed below. The runtime algebra concern from the stress-test note does not survive close reading: the substitution in Section 8 is algebraically correct. With the base case repaired and the parameter range of Theorem 1.2 made precise, the result would be a solid contribution.","major_comments":[{"comment":"The base case requires that, with high probability, B_l contains a neighbor of the highest-degree vertex p on the st path, where deg(p) is in [2^l, 2^{l+1}). The paper states 'With a high probability, there is a vertex, say w in B_l adjacent to p', but this does not follow from sampling each vertex into B_l with probability 1/2^l. For a fixed p with d = deg(p), the probability that no neighbor is sampled is (1 - 2^{-l})^d, which for d = 2^l is about e^{-1} and for d close to 2^{l+1} is about e^{-2}. These are constants, not the n^{-c} required by the paper's definition of 'with high probability'. Since a single B_l is used for all pairs and all high-degree vertices, the failure event must be controlled simultaneously for many p; a union bound over constant per-vertex failure probabilities cannot give n^{-c}. This base case is the anchor of the induction in Lemma 6.1, and Lemma 6.1 is the k = log n case of Theorem 1.2, so the central correctness guarantee is not established as written. The gap appears locally fixable, for example by sampling B_l with probability Theta(log n / 2^l), which would preserve the eO(n^2) running time, but the current text does not do this.","section":"Section 6.1, Algorithm 5"},{"comment":"Theorem 1.2 is stated for every k with log k >= 1, but the proof sets i = log log n - log k - 1 and then uses the objects A_{i+1}, ball_{i+1}(.), and pivot_{i+1}(.). These are defined only when 0 <= i+1 <= log log n - 1, i.e., when log k <= log log n. For log k > log log n the construction refers to undefined levels, so the theorem overclaims as stated. The paper should either restrict the statement to k <= log n or explicitly fall back on the known eO(n^2) bound for pairs at distance Omega(log n) when k is larger. This is a statement-range issue rather than a defect in the main small-k argument, but it must be corrected in the final version.","section":"Section 8 and Theorem 1.2"}],"minor_comments":[{"comment":"For the record, the runtime substitution in this section is algebraically correct: with i = log log n - log k - 1, the ball size eO(2^{2^{i+1}}) equals eO(2^{log n / k}) = eO(n^{1/k}), giving the stated eO(n^{2+1/k}). Adding one intermediate line here would prevent the reader from misreading the nested exponent.","section":"Section 8"},{"comment":"There are small bracket typos in displayed paths: in Lemma 7.3 the expression for est(pivot_{i+1}(q), vi) begins '|pivot_{i+1}(q), vi+1]' with a missing opening bracket, and in Section 8.2 the path '[pivot_{i+1}(z)], t]' has a misplaced bracket. These should be corrected.","section":"Section 7.3 and Section 8.2"},{"comment":"The notation for the sampling probabilities is easy to confuse: the text should consistently write 1/2^{2^i} (and eO(2^{2^i}) for ball sizes) with explicit braces, since the current rendering '1/2^{2i}' is ambiguous between 2^{2i} and 2^{2^i}. This matters for checking the probability calculations.","section":"Section 2, Definition 2.2"}],"recommendation":"major_revision","confidential_remarks":"The central idea is promising and the two issues I raise are both repairable: the base case can likely be fixed by sampling B_l at rate Theta(log n / 2^l), and the k-range can be restricted or handled by a fallback. I would not reject the paper, but the submitted version does not establish Theorem 1.2 as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The reader's take is right, and the stress-test note lands. Section 6.1 samples B_l with probability 2^{-l}. For the max-degree vertex p on the st path, with deg(p) in [2^l, 2^{l+1}), the expected number of sampled neighbors is between 1 and 2. That means the probability that B_l contains no neighbor of p is a constant (about e^{-1} at the low end), not the 1 - n^{-c} the paper's \"with high probability\" demands. The base case is the anchor of the induction in Lemma 6.1, so Theorem 1.2 for k = log n is not established. The general-k version inherits the same issue.\n\nSecond, the runtime derivation in Section 8 is algebraically off. Plugging i = log log n - log k - 1 into the ball-size term gives something like (log n)^2 / k^2, not n^{1/k}. The claimed eO(n^{2+1/k}) might be recoverable with a different parameter setting, but the substitution as written does not produce it.\n\nNow the credit. The ENSURE CLOSENESS idea is real: enforcing that the pivots are within constant distance of the st path, and using that to replace the k-apart requirement by O(log k), is a genuinely different approach from the DHZ/Roditty/SY line. The nested-pivot analysis is non-trivial, and the paper is well written, with the right citations and honest positioning. If the sampling issue is fixable — say, sampling B_l at a rate that guarantees log n sampled neighbors for degree-2^l vertices, at the cost of extra polylog factors — the result would be a genuine improvement that people would care about.\n\nWho gets value from this paper: anyone working on approximate APSP. It is a serious attempt at a 25-year-old tradeoff, and the structure is instructive even if flawed.\n\nMy recommendation for reviewing: I would not accept it as is, but I also would not desk-reject. Send it to a careful referee with the explicit request to test the base-case sampling. If the author can repair that, the paper deserves publication. If not, the central claim fails. The error is specific and visible, not a hidden contradiction, so a referee can quickly tell which way it goes.","headline":"Genuinely new ENSURE CLOSENESS approach, but the base case samples too sparsely to give high-probability correctness and the Section 8 runtime algebra doesn't close either.","tokens_in":22611,"tokens_out":4694,"would_cite":false,"duration_ms":52195,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68R10","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomized combinatorial algorithm computes 2-approximate shortest paths for all vertex pairs at distance at least O(log k) in $\\tilde{O}(n^{2+1/k})$ time, and $\\tilde{O}(n^2)$ time when $k = \\log n$.","keywords":["all-pairs shortest paths","2-approximation","undirected unweighted graphs","nested vertex sampling","pivot and ball arguments","randomized algorithm","near-quadratic time","combinatorial algorithm"],"falsifier":"Consider a graph where many $s,t$ pairs share a single highest-degree vertex $p$ of degree $d$ in $[2^\\ell, 2^{\\ell+1})$, with $p$ as the unique articulation on all short paths, and compute the probability that $B_\\ell$ contains no neighbor of $p$: it is $(1-1/2^\\ell)^d$, which lies between roughly $e^{-2}$ and $e^{-1}$ for all $n$; observing this constant failure rate for large $n$ would refute the claimed \"with high probability\" guarantee for all pairs.","tokens_in":21505,"feed_emoji":"⚡","tokens_out":13409,"duration_ms":130280,"temperature":0.7,"pith_summary":"The paper claims a new trade-off for approximate all-pairs shortest paths in undirected, unweighted graphs: a randomized combinatorial algorithm that, with high probability, outputs a distance at most twice the true one for every vertex pair whose distance is at least $O(\\log k)$, running in $\\tilde{O}(n^{2+1/k})$ time, where $\\log k \\ge 1$ is an integer. When $k = \\log n$, the runtime becomes $\\tilde{O}(n^2)$ and the guarantee covers all pairs at distance at least $O(\\log\\log n)$. If the theorem holds, this is the first improvement in over 25 years to the known $n^{2+O(1/k)}$-time trade-off, and it moves toward the open goal of a true quadratic-time 2-approximate APSP for all pairs. The argument uses nested random vertex sets, together with a subroutine that forces a certain pivot vertex to lie close to the shortest path, so that an induction over sampling levels accumulates only $O(\\log\\log n)$ additive error.","feed_headline":"2-approximate paths for close pairs in near-quadratic time","feed_subtitle":"For k=log n the algorithm reaches pairs just O(log log n) apart, beating the old O(log n) threshold.","key_machinery":"The central machinery is a family of nested random vertex sets $A_0 \\supseteq A_1 \\supseteq \\dots \\supseteq A_{\\log\\log n - 1}$, where $A_i$ keeps each vertex with probability $1/2^{2i}$. For each vertex $s$ and each level $i$, the algorithm computes $\\mathrm{pivot}_i(s)$, the nearest vertex of $A_i$ to $s$, and $\\mathrm{ball}_i(s)$, the set of vertices strictly closer to $s$ than that pivot; these balls are small with high probability. The inductive step maintains $\\mathrm{est}(u_i, v_i) \\le |a_i b_i| + 18(\\log\\log n - i)$, where $u_i = \\mathrm{pivot}_i(a_i)$ and $v_i = \\mathrm{pivot}_i(b_i)$ are pivots of vertices $a_i, b_i$ sitting on the $s$-$t$ path. The load-bearing subroutine ENSURE CLOSENESS first enforces that, unless a 2-approximation is already found, one of the pivots is within distance 3 of its path vertex; this lets each induction level bridge to the next through a short detour in a graph built from low-degree edges, pivot edges, and current estimates.","core_discovery":"The paper's central claim is Theorem 1.2: for every integer $\\log k \\ge 1$, there is a randomized combinatorial algorithm that with high probability computes 2-approximate distances for all vertex pairs at distance at least $O(\\log k)$, in $\\tilde{O}(n^{2+1/k})$ time. The special case $k = \\log n$ gives $\\tilde{O}(n^2)$ time for all pairs at distance at least $O(\\log\\log n)$. This improves the previous best-known trade-off, which only handled pairs at distance at least $k$ in the same kind of runtime, and it does so by a purely combinatorial route rather than by fast matrix multiplication.","pith_inferences":["A natural testable extension is to patch the base case by sampling neighbors of high-degree vertices more aggressively; if that can be done without increasing the $\\tilde{O}(n^2)$ runtime, the same framework would likely cover pairs at even smaller constant distance.","The nested pivot-and-ball induction is a general template that could be adapted to other additive approximation targets, such as $(2,\\beta)$-approximate APSP or approximate distance oracles, wherever a small set of sampled landmarks needs to stay close to arbitrary paths.","The additive constant 18 in the induction bound is not optimized; tightening the ball-size and closeness lemmas would lower the $O(\\log k)$ threshold, so the constant in the theorem's distance guarantee is likely improvable."],"forward_implications":["For $k = \\log n$, the theorem gives an $\\tilde{O}(n^2)$-time algorithm for all pairs at distance at least $O(\\log\\log n)$, improving the previous distance threshold from $O(\\log n)$ at the same runtime.","For a fixed integer $k$, the same algorithm gives 2-approximate distances in $\\tilde{O}(n^{2+1/k})$ time for pairs at distance at least $O(\\log k)$, with additive slack $18(\\log k + 1)$ that turns into a factor-2 bound once the true distance exceeds that amount.","The algorithm separates the cost of 2-approximation from that of $+k$-approximation for close pairs: the prior additive route needed pairs at distance $k$ to reach the same runtime, while the new method needs only $O(\\log k)$.","Because the algorithm is combinatorial, the stated running time does not depend on the fast-matrix-multiplication exponent, so the improvement is available even in settings where FMM-based algorithms are not used."],"supporting_citations":[{"why":"Baseline result whose $\\tilde{O}(n^{2+O(1/k)})$ trade-off for pairs at distance at least $k$ is what Theorem 1.2 improves; also supplies the $+k$-approximate APSP used in Observation 1.1.","marker":"[DHZ00]"},{"why":"Poses the question whether 2-approximation can beat $+k$-approximation for pairs at distance $k$, and provides a previous combinatorial 2-approximate APSP.","marker":"[Rod23]"},{"why":"Gives the latest FMM-based improvement for this problem, the running-time comparison point the new exponent is measured against.","marker":"[SY24]"},{"why":"Supplies the 2-approximate APSP algorithm the paper runs on the low-degree subgraph to handle paths whose edges all have small degree.","marker":"[BK06]"},{"why":"One of the $(2,1)$-approximate APSP algorithms the paper assumes as its base estimate $\\mathrm{est}(s,t) \\le 2|st| + 1$ for every pair.","marker":"[BK07]"}],"fun_headline_variants":["First 2-approx improvement: pairs O(log k) apart, not k","Combinatorial algorithm tightens 2-approx pair threshold","Same time, closer pairs: 2-approx paths improved","2-approx for pairs O(log k) apart, near-quadratic time","Closer pairs in same time: 2-approx shortest paths"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole induction depends on the base-case claim that the random set $B_\\ell$ contains a neighbor of the highest-degree path vertex $p$ with high probability, but when $p$'s degree lies in $[2^\\ell, 2^{\\ell+1})$ the expected number of sampled neighbors is only between 1 and 2, so the probability of missing all of them is a constant (roughly $e^{-1}$ to $e^{-2}$) rather than a high probability.","fun_headline_variants_meta":{"raw":{"variants":["First 2-approx improvement: pairs O(log k) apart, not k","Combinatorial algorithm tightens 2-approx pair threshold","Same time, closer pairs: 2-approx paths improved","2-approx for pairs O(log k) apart, near-quadratic time","Closer pairs in same time: 2-approx shortest paths"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000974,"raw_usage":{"total_tokens":4106,"prompt_tokens":877,"completion_tokens":3229,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":3134}},"tokens_in":493,"tokens_out":3229,"duration_ms":24134,"temperature":1.0,"reasoning_tokens":3134,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:01:07.873932+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Consider a graph where many $s,t$ pairs share a single highest-degree vertex $p$ of degree $d$ in $[2^\\ell, 2^{\\ell+1})$, with $p$ as the unique articulation on all short paths, and compute the probability that $B_\\ell$ contains no neighbor of $p$: it is $(1-1/2^\\ell)^d$, which lies between roughly $e^{-2}$ and $e^{-1}$ for all $n$; observing this constant failure rate for large $n$ would refute the claimed \"with high probability\" guarantee for all pairs.","supporting_citations":[],"review_version":1}