Pith. sign in

REVIEW 2 major objections 3 minor 28 references

Improved 2-Approximate Shortest Paths for close vertex pairs

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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$.

desk verdict 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. read the letter →

arxiv 2507.19859 v1 pith:MSGXDVWB submitted 2025-07-26 cs.DS

Manoj Gupta This is my paper · ORCID
classification cs.DS MSC 05C8568R1068W20
keywords all-pairsshortestpaths2-approximationundirectedunweightedgraphsnestedvertexsamplingpivotandballargumentsrandomizedalgorithmnear-quadratictimecombinatorial
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

2 major / 3 minor

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.

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 (2)
  1. [Section 6.1, Algorithm 5] 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.
  2. [Section 8 and Theorem 1.2] 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.
minor comments (3)
  1. [Section 8] 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.
  2. [Section 7.3 and Section 8.2] 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.
  3. [Section 2, Definition 2.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained, uses independent black-box algorithms, and the suspicious base-case sampling issue is a correctness gap, not a circular reduction.

full rationale

The paper's derivation chain does not reduce to its own inputs by construction. The main inductive argument (Lemma 6.1) is anchored on a base-case algorithm whose only external ingredients are standard nested vertex sampling and independent black-box (2,1)- and 2-approximate APSP results of [BK06, BK07, PR10, Som16, Knu17]. No parameter is fitted to the target vertex pairs, no estimate is renamed from a fitted quantity, and there are no load-bearing self-citations: the paper has a single author and its reference list contains no self-citations. The assumed bound est(s,t) <= 2|st|+1 is an external input, not a consequence of Theorem 1.2, and the paper does not invoke any prior work by the same author to justify its central technique. The base-case assertion in Section 6.1 that with high probability B_l contains a neighbor of the highest-degree vertex p is indeed not justified by the stated sampling rate: for deg(p) near 2^l the failure probability is a constant, so the claimed n^{-c} high-probability guarantee is not established. However, that is a probabilistic correctness gap, not a circular step: the claimed estimate is not equivalent to the input by definition, and the flawed step is an unproven sampling lemma rather than a fitted or self-referential premise. Accordingly, the circularity score is 0.

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

The central claim rests on standard sampling lemmas and prior approximations, plus one unjustified probabilistic assumption in the base case that likely breaks the high-probability guarantee.

assumptions (4)
  • standard math The nested sampling in Definition 2.2 gives |A_i| = eO(n/2^{2i}) with high probability.
    Lemma 2.3 follows from standard Chernoff bounds and the definition of nested sampling.
  • domain assumption A (2,1)-approximation of all-pairs shortest paths can be precomputed in eO(n^2) time.
    Used in Definition 2.1 and Lemma 5.1, citing prior work [BK07, PR10, Som16, Knu17].
  • domain assumption For pairs whose shortest path has only low-degree edges, running BK06 on the low-degree subgraph gives a 2-approximation for those pairs.
    Introduced in Section 2 before Assumption 2.8; this lets the paper focus on paths containing a high-degree vertex.
  • ad hoc to paper A random set B_l sampled with probability 1/2^l contains a neighbor of any vertex of degree in [2^l, 2^{l+1}) with high probability.
    This is the base-case claim in Section 6.1. It is not justified and appears false, as the expected number of sampled neighbors is only between 1 and 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved 2-Approximate Shortest Paths for close vertex pairs." pith.science (2026). https://pith.science/paper/MSGXDVWB

@misc{pith2026250719859,
  author       = {Pith},
  title        = {Pith review of: Improved 2-Approximate Shortest Paths for close vertex pairs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MSGXDVWB}},
  note         = {Machine review of arXiv:2507.19859}
}
abstract

An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in $\tilde{O}(n^{2+O\left(\frac{1}{k}\right )})$ time, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least $k$ apart, where $k \ge 2$. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same $\tilde{O}(n^{2+\frac{1}{k}})$ runtime but applies to vertex pairs merely $O(\log k)$ apart, where $\log k \ge 1$. When $k=\log n$, the running time of our algorithm is $\tilde{O}(n^2)$ and it works for all pairs at least $O(\log \log n)$ apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability.

Figures

Figures reproduced from arXiv: 2507.19859 by the authors.

Figure 1
Figure 1. A pictorial view of ui, ai, vi, bi. Lemma 2.10. For all 0 ⩽ i ⩽ log log n − 2, |sai| ⩽ |sai+1| and |tbi| ⩽ |tbi+1|. Also, note that there cannot be any vertex with degree Oe(2 2 i ) on the sai path, except maybe ai. If such a vertex x exists, then with a high probability there is a vertex of Ai adjacent to x, contradicting our choice of ui and ai. Thus, we have: Lemma 2.11. With high probability, for all 0 ⩽ i ⩽ log… view at source ↗
Figure 2
Figure 2. ENSURECLOSENESS ensures that (p, ai) or (q, bi) are close to each other. The reader may ask how does Lemma 3.3 help us remove Assumption 3.1 or ensure the weaker closeness condition in (3)? Let us assume that after executing ENSURECLOSENESS, est(s, t) > |st|. Also, let us assume 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. p is the vertex on the st path such that |sp| = |s pivoti+1(s)|. balli+1(ui) contains z which is close to p and p is close to ui+1. Lemma 3.4. Assume (A1) is true after the execution of ENSURECLOSENESS and |aiai+1| ⩾ 6 for some i ∈ [0 . . . log log n − 2]. Let p be the vertex on the st path at a distance |s pivoti+1(s)| from s. Let z be the vertex at a distance exactly 3 from p on sp path or at a distance ⩽ 6 from a… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [1]

    Fast estimation of diameter and shortest paths (without matrix multiplication)

    Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing , 28(4):1167--1181, 1999

    work page 1999

  2. [2]

    An almost 2-approximation for all-pairs of shortest paths in subquadratic time

    Maor Akav and Liam Roditty. An almost 2-approximation for all-pairs of shortest paths in subquadratic time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1--11. SIAM, 2020

    work page 2020

  3. [3]

    A refined laser method and faster matrix multiplication

    Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. TheoretiCS , 3, 2024

    work page 2024

  4. [4]

    Faster algorithms for approximate distance oracles and all-pairs small stretch paths

    Surender Baswana and Telikepalli Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages 591--602, Berkeley, CA, USA, 2006. IEEE

    work page 2006

  5. [5]

    Faster approximation of distances in graphs

    Piotr Berman and Shiva Prasad Kasiviswanathan. Faster approximation of distances in graphs. In Workshop on Algorithms and Data Structures , pages 541--552. Springer, 2007

    work page 2007

  6. [6]

    Approximate distance oracles with constant query time

    Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 654--663, 2014

    work page 2014

  7. [7]

    Approximate distance oracles with improved bounds

    Shiri Chechik. Approximate distance oracles with improved bounds. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages 1--10, 2015

    work page 2015

  8. [8]

    All-pairs small-stretch paths

    Edith Cohen and Uri Zwick. All-pairs small-stretch paths. Journal of Algorithms , 38(2):335--353, 2001

    work page 2001

Show all 28 references
  1. [9]

    Nearly 2-approximate distance oracles in subquadratic time

    Shiri Chechik and Tianyi Zhang. Nearly 2-approximate distance oracles in subquadratic time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 1...

    2022

  2. [10]

    Fast 2-approximate all-pairs shortest paths

    Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams , and Tijn de Vos. Fast 2-approximate all-pairs shortest paths. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandri...

    2024

  3. [11]

    All-pairs almost shortest paths

    Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing , 29(5):1740--1759, 2000

    2000

  4. [12]

    New additive approximations for shortest paths and cycles

    Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong. New additive approximations for shortest paths and cycles. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , 2022

    2022

  5. [13]

    Improved bounds for rectangular monotone min-plus product and applications

    Anita D \"u rr. Improved bounds for rectangular monotone min-plus product and applications. Information Processing Letters , 181:106358, 2023

    2023

  6. [14]

    Faster matrix multiplication via asymmetric hashing

    Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2129--2138. IEEE, 2023

    2023

  7. [15]

    Faster algorithms for all-pairs small stretch distances in weighted graphs

    Telikepalli Kavitha. Faster algorithms for all-pairs small stretch distances in weighted graphs. Algorithmica , 63(1):224--245, 2012

    2012

  8. [16]

    Additive spanners and distance oracles in quadratic time

    Mathias B k Tejs Knudsen. Additive spanners and distance oracles in quadratic time. CoRR , abs/1704.04473, 2017

    2017 arXiv

  9. [17]

    Powers of tensors and fast matrix multiplication

    Fran c ois Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation , pages 296--303, 2014

    2014

  10. [18]

    Distance oracles beyond the thorup-zwick bound

    Mihai Patrascu and Liam Roditty. Distance oracles beyond the thorup-zwick bound. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages 815--823. IEEE, 2010

    2010

  11. [19]

    New algorithms for all pairs approximate shortest paths

    Liam Roditty. New algorithms for all pairs approximate shortest paths. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 309--320. ACM , 2023

    2023

  12. [20]

    On the all-pairs-shortest-path problem in unweighted undirected graphs

    Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of computer and system sciences , 51(3):400--403, 1995

    1995

  13. [21]

    All-pairs approximate shortest paths and distance oracle preprocessing

    Christian Sommer. All-pairs approximate shortest paths and distance oracle preprocessing. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy , volume 55 of LIPIcs , pages 55:1--55:13, 2016

    2016

  14. [22]

    On the complexity of matrix multiplication

    Andrew James Stothers. On the complexity of matrix multiplication. 2010

    2010

  15. [23]

    Faster approximate all pairs shortest paths

    Barna Saha and Christopher Ye. Faster approximate all pairs shortest paths. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 4758--4827. SIAM , 2024

    2024

  16. [24]

    Compact routing schemes

    Mikkel Thorup and Uri Zwick. Compact routing schemes. In Arnold L. Rosenberg, editor, Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4-6, 2001 , pages 1--10. ACM , 2001

    2001

  17. [25]

    Multiplying matrices faster than coppersmith-winograd

    Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 887--898, 2012

    2012

  18. [26]

    Approximate distance oracles with improved preprocessing time

    Christian Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 202--208. SIAM, 2012

    2012

  19. [27]

    Approximate distance oracles with improved query time

    Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages 539--549. SIAM, 2013

    2013

  20. [28]

    New bounds for matrix multiplication: from alpha to omega

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3792--3835. SIAM, 2024

    2024

Pith tools

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