Pith. sign in

REVIEW 3 major objections 3 minor 242 references

A randomized algorithm computes a 2-approximation of all-pairs shortest paths in near-quadratic time for every vertex pair at distance at least a constant, cutting the excluded-distance threshold from O(log log n) to below 1000.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 14:34 UTC pith:U6DICJ6Y

load-bearing objection A plausible FMM-based route to constant excluded distance for 2-APSP, but the proof leans on two unproved modified lemmas from the first author's FOCS '25 paper and contains arithmetic slips; worth refereeing, not certifying as written. the 3 major comments →

arxiv 2607.18714 v1 pith:U6DICJ6Y submitted 2026-07-21 cs.DS

tilde{O}ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost

Manoj Gupta , Mrigankashekhar Shandilya This is my paper
classification cs.DS
keywords 2-approximate shortest pathsall-pairs shortest pathsfast matrix multiplicationnested vertex samplingrandomized algorithmsadditive approximationgraph algorithmsnear-quadratic time
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper tries to establish that a near-quadratic algorithm—running in ~O(n²) time with high probability—can 2-approximate shortest paths between every pair of vertices that are at least a constant distance apart. If true, this nearly resolves a central open question: previous near-quadratic algorithms only guaranteed 2-approximations for pairs separated by O(log n) or O(log log n) distances, and the only known lower bound is the quadratic output size. The paper achieves a constant threshold by splitting each shortest path into low-degree end segments, whose vertex degrees are small enough for exact local distance computation, and a short middle segment whose length is bounded by a constant (they get c ≤ 906). The proof blends combinatorial sampling arguments with fast rectangular matrix multiplication, and is the first to combine those tools to shrink the distance barrier to a constant.

Core claim

The central claim is Theorem 1.2: a randomized algorithm that, with high probability, runs in ~O(n²) time and computes a 2-approximation of all-pairs shortest paths for every pair of vertices at distance at least a constant c (taken as c = 906). The proof rests on the ball-proximity lemma (Theorem 4.1), which guarantees that after a preprocessing routine the two boundary vertices p_s and p_t on a shortest path lie within a constant distance of each other. The algorithm then checks close candidate pairs directly when there are few of them (sparse case) and, when many vertices are close, uses a small random sample plus an approximate min-plus product to piece together the path. The improvement

What carries the argument

The load-bearing object is the modified nested vertex sampling process (Definition 3.6), which starts from an intermediate sample set A_α whose balls and clusters both have size ~O(2^{2α}); this preserves exact distance computations inside balls while bounding the clusters the algorithm enumerates. The ball-proximity lemma (Theorem 4.1) then forces the middle segment p_s p_t to have constant length, decomposing every shortest path into a low-degree prefix, a constant-length middle, and a low-degree suffix. The dense case is handled by an approximate min-plus product over a random sample L_γ; since the inner dimension is n^{0.125}, known rectangular matrix multiplication bounds give ~O(n²) ti

Load-bearing premise

The load-bearing premise is that the two modified lemmas imported from the earlier O(log log n) paper—one about the per-level closeness invariant, one about the u_i–v_i estimate bound—still hold when sampling starts at the intermediate level A_α rather than at the base level; the paper asserts their proofs are 'identical' but does not actually write them out.

What would settle it

Run the modified sampling and MODIFIEDENSURECLOSENESS from Section 6 on graphs where high-degree vertices are arranged so that the first α-level sample misses the neighborhood of some high-degree vertex on a shortest path; if for any pair s,t the inequality |sa_α| − |s pivot_α(s)| ≤ 3 or the corresponding |tb_α| − |t pivot_α(t)| ≤ 3 fails, Lemma 6.2 is false, and the ball-proximity lemma (Theorem 4.1) that powers the constant-distance claim collapses.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the theorem is correct, near-quadratic-time 2-approximate APSP is resolved for all but a constant-distance slice of vertex pairs, making the remaining gap purely about pairs within distance ≤ 906.
  • The algorithm runs in ~O(n²) time with high probability, so the output-size lower bound Θ(n²) is met up to polylogarithmic factors for all pairs outside the constant-distance cutoff.
  • The use of fast matrix multiplication is essential to the dense case; a purely combinatorial algorithm at this threshold would need to replace the min-plus product step.
  • By Observation 1.1, the constant additive approximation produced for close pairs yields a valid 2-approximation for all pairs at distance at least the same constant, giving a clean end-to-end guarantee.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A natural extension would be to see if the intermediate-level sampling start can be pushed even closer to the top level, which would reduce the constant 906 further; the paper states it made no attempt to optimize constants.
  • The sparse/dense tradeoff suggests a template for other approximation problems: if the set of 'useful' witnesses is small, enumerate them; if large, random sampling plus fast matrix multiplication becomes cheaper than enumeration. This could apply to approximate distance oracles or to diameter approximations.
  • If one could re-derive Lemmas 6.2 and 6.4 without relying on the earlier paper's machinery, the proof would become self-contained; until then, a reader betting on the theorem should treat the constant-distance result as contingent on those two black-box lemmas.
  • A testable computational check: implement MODIFIEDENSURECLOSENESS on families of dense graphs near the degree threshold and empirically verify the sampled-pivot invariant; a failure would show up as a pair with an over-large ball boundary gap.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper claims a randomized algorithm that, with high probability, runs in O~(n^2) time and computes a 2-approximation of all-pairs shortest paths for every pair at distance at least a constant c (the text establishes c ≤ 906). This would improve the previous excluded-distance barrier of O(log log n) (Gupta, FOCS 2025) to a constant, nearly resolving the central open question of whether 2-APSP can be solved in near-quadratic time. The algorithm combines combinatorial techniques from Gupta [Gup25] with fast rectangular matrix multiplication: it splits the shortest path into a low-degree prefix and suffix, uses a sparse/dense case split on the set of estimated-close vertices, and applies a min-plus product to handle the dense case. The main technical lemma (Theorem 4.1) asserts a ball-proximity property that bounds the middle segment of the shortest path by a constant; its proof in Section 6 relies on two modified versions of lemmas from [Gup25] (Lemmas 6.2 and 6.4) that are asserted to follow by 'identical' proofs but are not proved in the manuscript.

Significance. If the proof can be completed, the result is highly significant: it reduces the distance threshold in the O~(n^2)-time 2-APSP problem from O(log log n) to a constant, essentially closing the gap to the all-pairs case modulo a constant excluded distance. The combination of combinatorial ball/cluster techniques with FMM for the dense case is novel and the sparse/dense split is elegant. The paper also contains full proofs for several auxiliary lemmas (e.g., the Thorup–Zwick sampling construction in Appendix A), and pseudocode for the main algorithms. However, the central ball-proximity theorem is not self-contained because its proof depends on unproved modifications of results from the author's own prior work; this must be addressed before the result can be accepted.

major comments (3)
  1. [Section 6, Lemmas 6.2 and 6.4] Lemmas 6.2 and 6.4 are asserted to hold with proofs 'identical' to [Gup25], but no proof or detailed reduction is given. The modified sampling hierarchy starts at A_α obtained by a different Thorup–Zwick procedure (Definition 3.6), whereas the original lemmas apply to the hierarchy starting at A_1 (Definition 3.2). It is not shown that the downward induction in [Gup25] survives truncation to i ≥ α, nor that the change in the construction of the base level does not affect the properties used. Since Equation (4) and Theorem 4.1 rest directly on these lemmas, the central claim is not self-contained. The authors must provide full proofs or a precise step-by-step adaptation.
  2. [Section 4.1, runtime derivation] The runtime calculation contains a false arithmetic equality: 2^{2 log log n − 3} = 2^{(log n)/8}. In fact 2^{2 log log n − 3} = Θ((log n)^2), which is far smaller than n^{0.125}. The final conclusion O~(n^2) still follows because the correct expression is smaller than the claimed n^{0.125}, but the derivation as written is invalid and must be corrected.
  3. [Appendix B, probability computation] The derivation Pr[v∈A_{i+1}(1)] = Pr[v∈A_i(1)] · 2^{-2^i} = 2^{-2^i} · 2^{-2^i} = 2^{-2^{i+1}} appears to conflict with the sampling probabilities stated in Definitions 3.2/3.6. Please state the exact transition probabilities and give a consistent induction. Lemma 3.7, which is used to prove existence of the a_i, b_i vertices and the low-degree path property, depends on this calculation.
minor comments (3)
  1. [Definition 3.2] The sampling probabilities are typeset ambiguously (e.g., '1/22i−1'). Please use unambiguous notation such as 1/2^{2^i} or 1/2^{2^{i−1}} throughout, and ensure consistency between the definition and the proofs in Appendices B and C.
  2. [Lemma 4.7] The claim that every vertex at distance strictly less than 2c+1 from p_s has degree at most 2γ should explicitly justify that all neighbors of such a vertex lie within TRUECLOSE(p_s). The current statement is terse; the argument is correct for vertices on the p_s z path, but the proof would be clearer with this detail.
  3. [Assumption 3.1] The paper says it 'assumes' the shortest st path contains a vertex of degree Ω~(√n). This is a case split, not an assumption: if the path is entirely low-degree, the Baswana–Kavitha subroutine on the low-degree subgraph applies. A short sentence explaining the reduction would improve readability.

Circularity Check

1 steps flagged

Central ball-proximity theorem rests on two modified lemmas (6.2, 6.4) imported from [Gup25] with 'identical' proofs but no derivation for the modified sampling start.

specific steps
  1. self citation load bearing [Section 6, Lemmas 6.2 and 6.4; Section 6.3 proof of Theorem 4.1]
    "The only change from Theorem 6.1 is the lower limit of the range: α⩽i instead of 0⩽i. The algorithm MODIFIEDENSURECLOSENESS and its proof remain identical to those in [Gup25]. ... Again, the algorithm and the proof of the above lemma remain the same as in [Gup25]. The only change is that we run the algorithm of [Gup25] for fewer iterations."

    ENSUREBALLPROXIMITY is the linchpin: Theorem 4.1 -> Lemma 4.4 -> constant-distance bound -> the 2-APSP claim. Its proof uses Equation (4), which is obtained only after invoking Lemma 6.4; Lemma 6.4 (and Lemma 6.2) are asserted to be identical to [Gup25] after changing the sampling start from A_1/A_0 to A_α. The paper supplies no argument that the original induction survives truncation, so the central constant-distance bound is carried by an unverified self-citation chain instead of a derivation contained in this paper.

full rationale

The paper's new algorithmic contribution, the sparse/dense split with fast matrix multiplication and the Thorup-Zwick-style bounded-cluster set A_alpha, is not itself circular and relies on standard external tools (BK06, TZ01, Zwick, rectangular matrix multiplication bounds). However, the proof of the headline constant-distance guarantee is not self-contained: Theorem 4.1, which powers Lemmas 4.3-4.4 and therefore the final constant c, is established in Section 6 only by importing two modified lemmas from the first author's prior work [Gup25]. The paper repeatedly says the algorithms and proofs are 'identical' to [Gup25] after changing the lower index from 0 to alpha, but does not prove that the original induction survives when the hierarchy starts at A_alpha rather than at the full base hierarchy. This is load-bearing self-citation: the new theorem depends on an unverified modification of the authors' own prior lemmas. There is no fitted parameter renamed as a prediction, no definitional equivalence, and no renaming of a known result, so the circularity score should be moderate rather than extreme. The arithmetic inconsistency in Section B's probability calculation is a correctness concern, not a circularity.

Axiom & Free-Parameter Ledger

6 free parameters · 7 axioms · 0 invented entities

The central claim rests on a borrowed sampling framework (Gupta 2025) plus several externally cited algorithmic lemmas. The main free parameters are algorithmic constants chosen for runtime tradeoffs rather than fitted to data. The most fragile imports are the modified Lemmas 6.2 and 6.4, which are not proven in this paper.

free parameters (6)
  • alpha = log log n - 4
    Level of the modified nested sampling hierarchy; chosen so that clusters are polylog and ENSUREBALLPROXIMITY has ~O(n^2) runtime. The value affects the final constant 906.
  • gamma levels = {n^0.875, 2n^0.875, 4n^0.875, ..., n}
    Dense-case sampling thresholds; balance the size of the random sample against the matrix-multiplication inner dimension n/gamma.
  • epsilon = 1/2
    Approximation parameter for the min-plus product; chosen so the final estimate is a 2-approximation for distances at least 12c+6.
  • c' = 37
    Constant in the ball-proximity inequality; derived from the 18(log log n - alpha) + 74 terms.
  • c and distance threshold = c=75, threshold=12c+6=906
    Final constant-distance guarantee; a consequence of c' and the epsilon choice.
  • sparse/dense threshold exponent = 0.875
    Threshold for |ESTIMATEDCLOSE(x)|; chosen so the sparse-case enumeration stays within ~O(n^2) and the dense case has inner dimension n^0.125 for FMM.
axioms (7)
  • domain assumption Lemma 3.4 from [Gup25]
    Gives ball-size bounds, exact distances inside balls, and ~O(n^2) preprocessing for the modified sampling hierarchy. The paper sketches a proof in Appendix C, but relies on prior-work structure.
  • ad hoc to paper Lemmas 6.2 and 6.4 (modified ENSURE... from [Gup25])
    Asserted with proofs 'identical' to [Gup25] but not reproduced; the central ball-proximity guarantee depends on these modified versions that start sampling at A_alpha instead of A_1.
  • domain assumption Thorup-Zwick Lemma A.3
    FINDCENTERS terminates in expected ~O(1) iterations and cluster sizes are O(2^{2alpha}); external standard result used for the bounded-cluster construction.
  • domain assumption Zwick Lemma 3.11 (approximate min-plus product)
    External result used to compute the dense-case distance product in ~O(n^2) time.
  • domain assumption omega(0.125)=2 [Cop82, Wil14]
    Rectangular matrix multiplication with inner dimension n^0.125 runs in ~O(n^2); needed for the dense-case running time.
  • ad hoc to paper Assumption 3.1
    After handling low-degree paths separately, every remaining shortest path has a vertex of degree at least ~O(sqrt(n)); this is a justified reduction but still an assumption on the residual problem.
  • standard math Chernoff/concentration bounds
    Used throughout for high-probability bounds on balls, clusters, and sampled sets.

pith-pipeline@v1.3.0-alltime-deepseek · 21994 in / 26882 out tokens · 207007 ms · 2026-08-01T14:34:49.035840+00:00 · methodology

0 comments
read the original abstract

Given an undirected, unweighted graph $G$, we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of $\Omega(n^2)$ since the output size is $\Theta(n^2)$. A central goal in this area is to achieve a running time of $O(n^2)$. Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2001) designed an algorithm with a running time of $\tilde{O}(n^2)$ that guarantees a 2-approximation only for pairs at a distance of at least $O(\log n)$. Recently, Gupta (FOCS 2025) improved this bound, handling all pairs at a distance of at least $O(\log \log n)$. We nearly resolve this problem. We design a randomized algorithm that runs in $\tilde{O}(n^2)$ time and, with high probability, guarantees a 2-approximation for all pairs at distance at least $c$, where $c \ge 0$ is a constant. Unlike the above two results, which were purely combinatorial, our algorithm combines combinatorial techniques with fast matrix multiplication (FMM).

Figures

Figures reproduced from arXiv: 2607.18714 by Manoj Gupta, Mrigankashekhar Shandilya.

Figure 1
Figure 1. Figure 1: Vertices ps and pt lie on the boundary of ballA(s) and ballA(t) respectively and lie on the st path. Using Theorem 2.4, each vertex on the sps path, except possibly ps, has degree ⩽ O˜ (n 0.05). We make the same argument for the vertices on the ptt path. Thus, the prefix sps and the suffix ptt of the st path have low degree, and we will use this crucially to design faster algorithms. But what about the mid… view at source ↗
Figure 2
Figure 2. Figure 2: Figure shows the relative position of ai’s, ui’s, bi’s and vi’s along the st path In [Gup25], the vertices ai, ui, bi, vi are defined for all i ⩾ 0. Since our modified vertex sampling starts from α, we define these terms only for i ⩾ α. We first show that, for each i ⩾ α, the vertex ai exists. For this, we rely on Theorem 3.1, which states that there is a vertex of degree at least O˜ ( √ n) on the st path.… view at source ↗
Figure 3
Figure 3. Figure 3: A diagram showing the relation between ps, aα, uα and pt, vα, bα If t ∈ ballα(s), then using Theorem 3.4, est(s, t) = |st|. Henceforth, we will assume that t /∈ ballα(s) and s /∈ ballα(t). We now show several properties of ps and pt that our algorithm will use. Recall that we defined the vertices aα and bα on the st path. We now describe the relation between ps and aα and between pt and bα. Lemma 4.3. Vert… view at source ↗
Figure 4
Figure 4. Figure 4: The figure illustrates the scenario discussed in this section. The vertex [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

242 extracted references · 3 canonical work pages

  1. [1]

    Journal of the ACM , volume =

    Ryan Williams , title =. Journal of the ACM , volume =. 2014 , doi =

    2014

  2. [2]

    SIAM Journal on Computing , volume =

    Don Coppersmith , title =. SIAM Journal on Computing , volume =. 1982 , doi =

    1982

  3. [3]

    Journal of Complexity , volume =

    Don Coppersmith , title =. Journal of Complexity , volume =. 1997 , doi =

    1997

  4. [4]

    Improved Additive Approximation Algorithms for

    Ce Jin and Yael Kirkpatrick and Michal Stawarz and Virginia. Improved Additive Approximation Algorithms for. Proceedings of the 2026 Annual

    2026

  5. [5]

    Incremental Topological Sort and Cycle Detection in Expected Total Time , year =

    Aaron Bernstein and Shiri Chechik , booktitle =. Incremental Topological Sort and Cycle Detection in Expected Total Time , year =

  6. [6]

    An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model , year =

    Surender Baswana and Keerti Choudhary and Liam Roditty , booktitle =. An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model , year =. doi:10.4230/LIPIcs.ICALP.2017.72 , timestamp =

    doi:10.4230/lipics.icalp.2017.72 2017

  7. [7]

    Workshop on Algorithms and Data Structures , pages=

    Faster approximation of distances in graphs , author=. Workshop on Algorithms and Data Structures , pages=. 2007 , organization=

    2007

  8. [8]

    2010 , publisher=

    On the complexity of matrix multiplication , author=. 2010 , publisher=

    2010

  9. [9]

    Algorithmica , volume=

    Faster algorithms for all-pairs small stretch distances in weighted graphs , author=. Algorithmica , volume=. 2012 , publisher=

    2012

  10. [10]

    Nearly 2-Approximate Distance Oracles in Subquadratic Time , booktitle =

    Shiri Chechik and Tianyi Zhang , editor =. Nearly 2-Approximate Distance Oracles in Subquadratic Time , booktitle =

  11. [11]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    An almost 2-approximation for all-pairs of shortest paths in subquadratic time , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  12. [12]

    Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35 , pages=

    Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error , author=. Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35 , pages=. 2008 , organization=

    2008

  13. [13]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Faster matrix multiplication via asymmetric hashing , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  14. [14]

    SIAM Journal on Computing , volume=

    Fast estimation of diameter and shortest paths (without matrix multiplication) , author=. SIAM Journal on Computing , volume=. 1999 , publisher=

    1999

  15. [15]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    New bounds for matrix multiplication: from alpha to omega , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  16. [16]

    TheoretiCS , volume=

    A refined laser method and faster matrix multiplication , author=. TheoretiCS , volume=. 2024 , publisher=

    2024

  17. [17]

    Journal of computer and system sciences , volume=

    On the all-pairs-shortest-path problem in unweighted undirected graphs , author=. Journal of computer and system sciences , volume=. 1995 , publisher=

    1995

  18. [18]

    Journal of Algorithms , volume=

    All-pairs small-stretch paths , author=. Journal of Algorithms , volume=. 2001 , publisher=

    2001

  19. [19]

    All-pairs nearly 2-approximate shortest paths in

    Baswana, Surender and Goyal, Vishrut and Sen, Sandeep , journal=. All-pairs nearly 2-approximate shortest paths in. 2009 , publisher=

    2009

  20. [20]

    43rd International Colloquium on Automata, Languages, and Programming,

    Christian Sommer , title =. 43rd International Colloquium on Automata, Languages, and Programming,

  21. [21]

    CoRR , title =

    Aaron Bernstein and Danupon Nanongkai and Christian Wulff. CoRR , title =. 2022 , volume =. doi:10.48550/arXiv.2203.03456 , eprint =

    Pith/arXiv arXiv doi:10.48550/arxiv.2203.03456 2022

  22. [22]

    A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths , year =

  23. [23]

    Dynamic Set Cover: Improved Amortized and Worst-Case Update Time , year =

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai and Xiaowei Wu , booktitle =. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time , year =

  24. [24]

    Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs , year =

    Andr. Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs , year =

  25. [25]

    Information Processing Letters , volume=

    Improved bounds for rectangular monotone min-plus product and applications , author=. Information Processing Letters , volume=. 2023 , publisher=

    2023

  26. [26]

    Fast 2-Approximate All-Pairs Shortest Paths , booktitle =

    Michal Dory and Sebastian Forster and Yael Kirkpatrick and Yasamin Nazari and Virginia. Fast 2-Approximate All-Pairs Shortest Paths , booktitle =

  27. [27]

    New Algorithms for All Pairs Approximate Shortest Paths , booktitle =

    Liam Roditty , editor =. New Algorithms for All Pairs Approximate Shortest Paths , booktitle =

  28. [28]

    Faster Approximate All Pairs Shortest Paths , booktitle =

    Barna Saha and Christopher Ye , editor =. Faster Approximate All Pairs Shortest Paths , booktitle =

  29. [29]

    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , year=

    New additive approximations for shortest paths and cycles , author=. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , year=

    2022

  30. [30]

    SIAM Journal on Computing , volume=

    All-pairs almost shortest paths , author=. SIAM Journal on Computing , volume=. 2000 , publisher=

    2000

  31. [31]

    Distributed weighted min-cut in nearly-optimal time , year =

    Michal Dory and Yuval Efron and Sagnik Mukhopadhyay and Danupon Nanongkai , booktitle =. Distributed weighted min-cut in nearly-optimal time , year =

  32. [32]

    Vertex connectivity in poly-logarithmic max-flows , year =

    Jason Li and Danupon Nanongkai and Debmalya Panigrahi and Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai , booktitle =. Vertex connectivity in poly-logarithmic max-flows , year =

  33. [33]

    A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond , year =

    Julia Chuzhoy and Yu Gao and Jason Li and Danupon Nanongkai and Richard Peng and Thatchaphol Saranurak , booktitle =. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond , year =

  34. [34]

    Weighted min-cut: sequential, cut-query, and streaming algorithms , year =

    Sagnik Mukhopadhyay and Danupon Nanongkai , booktitle =. Weighted min-cut: sequential, cut-query, and streaming algorithms , year =

  35. [35]

    Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary , year =

    Aaron Bernstein and Jan van den Brand and Maximilian Probst Gutenberg and Danupon Nanongkai and Thatchaphol Saranurak and Aaron Sidford and He Sun , journal =. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary , year =. arXiv , bibsource =:2004.08432 , url =

    Pith/arXiv arXiv 2004

  36. [36]

    Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time , year =

    Jan van den Brand and Danupon Nanongkai , booktitle =. Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time , year =

  37. [37]

    Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds , year =

    Jan van den Brand and Danupon Nanongkai and Thatchaphol Saranurak , booktitle =. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds , year =

  38. [38]

    Distributed exact weighted all-pairs shortest paths in near-linear time , year =

    Aaron Bernstein and Danupon Nanongkai , booktitle =. Distributed exact weighted all-pairs shortest paths in near-linear time , year =

  39. [39]

    Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time , year =

  40. [40]

    A Faster Distributed Single-Source Shortest Paths Algorithm , year =

    Sebastian Forster and Danupon Nanongkai , booktitle =. A Faster Distributed Single-Source Shortest Paths Algorithm , year =

  41. [41]

    Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks , year =

  42. [42]

    Distributed Exact Weighted All-Pairs Shortest Paths in

    Chien. Distributed Exact Weighted All-Pairs Shortest Paths in. 58th. 2017 , editor =

    2017

  43. [43]

    Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time , year =

    Danupon Nanongkai and Thatchaphol Saranurak and Christian Wulff. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time , year =. 58th

  44. [44]

    Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n\(

    Danupon Nanongkai and Thatchaphol Saranurak , booktitle =. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n\(. 2017 , editor =

    2017

  45. [45]

    Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization , year =

  46. [46]

    New deterministic approximation algorithms for fully dynamic matching , year =

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai , booktitle =. New deterministic approximation algorithms for fully dynamic matching , year =

  47. [47]

    Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , booktitle =. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs , year =. doi:10.1007/978-3-662-47672-7\_59 , url =

    doi:10.1007/978-3-662-47672-7

  48. [48]

    Tsourakakis , booktitle =

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai and Charalampos E. Tsourakakis , booktitle =. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams , year =

  49. [49]

    Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai and Thatchaphol Saranurak , booktitle =. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , year =

  50. [50]

    Faster Algorithms for Semi-Matching Problems , year =

    Jittat Fakcharoenphol and Bundit Laekhanukit and Danupon Nanongkai , journal =. Faster Algorithms for Semi-Matching Problems , year =

  51. [51]

    Almost-Tight Distributed Minimum Cut Algorithms , year =

    Danupon Nanongkai and Hsin. Almost-Tight Distributed Minimum Cut Algorithms , year =. Distributed Computing - 28th International Symposium,. doi:10.1007/978-3-662-45174-8\_30 , url =

    doi:10.1007/978-3-662-45174-8

  52. [52]

    2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=

    Distance oracles beyond the Thorup-Zwick bound , author=. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages=. 2010 , organization=

    2010

  53. [53]

    Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

    Approximate distance oracles with improved bounds , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

  54. [54]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Approximate distance oracles with constant query time , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  55. [55]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Approximate distance oracles with improved query time , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  56. [56]

    Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Approximate distance oracles with improved preprocessing time , author=. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2012 , organization=

    2012

  57. [57]

    Additive Spanners and Distance Oracles in Quadratic Time , journal =

    Mathias B. Additive Spanners and Distance Oracles in Quadratic Time , journal =. 2017 , url =. 1704.04473 , timestamp =

    Pith/arXiv arXiv 2017

  58. [59]

    Theory Comput

    Sayan Bhattacharya and Wolfgang Dvor. Theory Comput. Syst. , title =. 2017 , number =

    2017

  59. [60]

    Weighted dynamic finger in binary search trees , year =

    John Iacono and Stefan Langerman , booktitle =. Weighted dynamic finger in binary search trees , year =. doi:10.1137/1.9781611974331.ch49 , groups =

    doi:10.1137/1.9781611974331.ch49

  60. [61]

    42nd Annual Symposium on Foundations of Computer Science,

    John Hershberger and Subhash Suri , title =. 42nd Annual Symposium on Foundations of Computer Science,. 2001 , pages =

    2001

  61. [62]

    Distributed Computing - 28th International Symposium,

    Merav Parter , title =. Distributed Computing - 28th International Symposium,. 2014 , pages =

    2014

  62. [63]

    Upper bounds for time-space trade-offs in sorting and selection , year =

    Frederickson, Greg N , journal =. Upper bounds for time-space trade-offs in sorting and selection , year =

  63. [64]

    Upper Bounds for Maximally Greedy Binary Search Trees , year =

    Kyle Fox , booktitle =. Upper Bounds for Maximally Greedy Binary Search Trees , year =

  64. [65]

    Lawrence and Wegman, Mark N

    Carter, J. Lawrence and Wegman, Mark N. , title =. Proceedings of the Ninth Annual ACM Symposium on Theory of Computing , year =. doi:10.1145/800105.803400 , location =

    arXiv

  65. [66]

    Truthful unit-demand auctions with budgets revisited , year =

    Monika Henzinger and Veronika Loitzenbauer , journal =. Truthful unit-demand auctions with budgets revisited , year =

  66. [67]

    Towards polynomial lower bounds for dynamic problems , year =

    Mihai Patrascu , booktitle =. Towards polynomial lower bounds for dynamic problems , year =

  67. [68]

    The State of the Art in Dynamic Graph Algorithms , year =

    Monika Henzinger , booktitle =. The State of the Art in Dynamic Graph Algorithms , year =

  68. [69]

    The Power of Vertex Sparsifiers in Dynamic Graph Algorithms , year =

    Gramoz Goranci and Monika Henzinger and Pan Peng , booktitle =. The Power of Vertex Sparsifiers in Dynamic Graph Algorithms , year =

  69. [70]

    The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree , year =

    Jakub Lacki and Jakub Ocwieja and Marcin Pilipczuk and Piotr Sankowski and Anna Zych , booktitle =. The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree , year =

  70. [71]

    The power of deferral: maintaining a constant-competitive steiner tree online , year =

    Albert Gu and Anupam Gupta and Amit Kumar , booktitle =. The power of deferral: maintaining a constant-competitive steiner tree online , year =

  71. [72]

    Bender and Martin Farach

    Michael A. Bender and Martin Farach. The. 2000 , pages =

    2000

  72. [73]

    The k most vital arcs in the shortest path problem , year =

    Malik, Kavindra and Mittal, Ashok K and Gupta, Santosh K , journal =. The k most vital arcs in the shortest path problem , year =

  73. [74]

    The discrepancy method - randomness and complexity , year =

    Bernard Chazelle , publisher =. The discrepancy method - randomness and complexity , year =

  74. [75]

    and Hopcroft, John E

    Aho, Alfred V. and Hopcroft, John E. , publisher =. The Design and Analysis of Computer Algorithms , year =

  75. [76]

    Symbolic algorithms for qualitative analysis of Markov decision processes with B

    Krishnendu Chatterjee and Monika Henzinger and Manas Joglekar and Nisarg Shah , journal =. Symbolic algorithms for qualitative analysis of Markov decision processes with B. 2013 , number =

    2013

  76. [77]

    Subquadratic dynamic path reporting in directed graphs against an adaptive adversary , year =

    Adam Karczmarz and Anish Mukherjee and Piotr Sankowski , booktitle =. Subquadratic dynamic path reporting in directed graphs against an adaptive adversary , year =

  77. [78]

    Ryan , journal =

    Williams, Virginia Vassilevska and Williams, R. Ryan , journal =. Subcubic Equivalences Between Path, Matrix, and Triangle Problems , year =

  78. [79]

    Italiano and Amnon Nissenzweig , journal =

    David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon Nissenzweig , journal =. Sparsification: A technique for speeding up dynamic graph algorithms , year =

  79. [80]

    Sparse Fault-Tolerant

    Merav Parter and David Peleg , booktitle =. Sparse Fault-Tolerant. 2013 , pages =

    2013

  80. [81]

    Space--time trade-offs for stack-based algorithms , year =

    Barba, Luis and Korman, Matias and Langerman, Stefan and Sadakane, Kunihiko and Silveira, Rodrigo I , journal =. Space--time trade-offs for stack-based algorithms , year =

Showing first 80 references.