Pith. sign in

REVIEW 3 major objections 3 minor 242 references

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

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

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

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

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

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

Manoj Gupta , Mrigankashekhar Shandilya This is my paper · ORCID
classification cs.DS
keywords 2-approximateshortestpathsall-pairsfastmatrixmultiplicationnestedvertexsamplingrandomizedalgorithmsadditiveapproximationgraphnear-quadratictime
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

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.

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

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

Extended reading notes

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

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.

Editorial extensions

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.

Reading between the lines

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

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 · score 5.0 of 10

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.

  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.

Assumptions & free parameters 6 free parameters · 7 assumptions · 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.
assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of $\tilde{O}$ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost." pith.science (2026). https://pith.science/paper/U6DICJ6Y

@misc{pith2026260718714,
  author       = {Pith},
  title        = {Pith review of: $\tildeO$ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U6DICJ6Y}},
  note         = {Machine review of arXiv:2607.18714}
}
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 the authors.

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 middle segmen… view at source ↗
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. Let z be … view at source ↗
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. Vertex ps lies… view at source ↗
Figures from the paper (1 more)
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]

Discussion (0). Continue with ORCID to comment.

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

Show all 242 references
  1. [9]

    Algorithmica , volume=

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

    2012

  2. [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 =

  3. [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

  4. [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

  5. [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

  6. [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

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

  8. [16]

    TheoretiCS , volume=

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

    2024

  9. [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

  10. [18]

    Journal of Algorithms , volume=

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

    2001

  11. [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

  12. [20]

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

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

  13. [21]

    CoRR , title =

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

    2022 doi arXiv

  14. [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 =

  15. [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 =

  16. [24]

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

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

  17. [25]

    Information Processing Letters , volume=

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

    2023

  18. [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 =

  19. [27]

    New Algorithms for All Pairs Approximate Shortest Paths , booktitle =

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

  20. [28]

    Faster Approximate All Pairs Shortest Paths , booktitle =

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

  21. [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

  22. [30]

    SIAM Journal on Computing , volume=

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

    2000

  23. [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 =

  24. [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 =

  25. [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 =

  26. [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 =

  27. [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 =

    2004 arXiv

  28. [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 =

  29. [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 =

  30. [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 =

  31. [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 =

  32. [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 =

  33. [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 =

  34. [42]

    Distributed Exact Weighted All-Pairs Shortest Paths in

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

    2017

  35. [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

  36. [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

  37. [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 =

  38. [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 =

  39. [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

  40. [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 =

  41. [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 =

  42. [50]

    Faster Algorithms for Semi-Matching Problems , year =

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

  43. [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

  44. [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

  45. [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=

  46. [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=

  47. [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

  48. [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

  49. [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 =

    2017 arXiv

  50. [59]

    Theory Comput

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

    2017

  51. [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

  52. [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

  53. [62]

    Distributed Computing - 28th International Symposium,

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

    2014

  54. [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 =

  55. [64]

    Upper Bounds for Maximally Greedy Binary Search Trees , year =

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

  56. [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 =

  57. [66]

    Truthful unit-demand auctions with budgets revisited , year =

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

  58. [67]

    Towards polynomial lower bounds for dynamic problems , year =

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

  59. [68]

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

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

  60. [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 =

  61. [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 =

  62. [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 =

  63. [72]

    Bender and Martin Farach

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

    2000

  64. [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 =

  65. [74]

    The discrepancy method - randomness and complexity , year =

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

  66. [75]

    and Hopcroft, John E

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

  67. [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

  68. [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 =

  69. [78]

    Ryan , journal =

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

  70. [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 =

  71. [80]

    Sparse Fault-Tolerant

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

    2013

  72. [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 =

  73. [82]

    Simultaneously Load Balancing for Every p-norm, With Reassignments , year =

    Aaron Bernstein and Tsvi Kopelowitz and Seth Pettie and Ely Porat and Clifford Stein , booktitle =. Simultaneously Load Balancing for Every p-norm, With Reassignments , year =. doi:10.4230/LIPIcs.ITCS.2017.51 , groups =

    2017 doi

  74. [83]

    Simple deterministic algorithms for fully dynamic maximal matching , year =

    Ofer Neiman and Shay Solomon , booktitle =. Simple deterministic algorithms for fully dynamic maximal matching , year =

  75. [84]

    Shortest paths in directed planar graphs with negative lengths: A linear-space O (n log 2 n)-time algorithm , year =

    Klein, Philip N and Mozes, Shay and Weimann, Oren , journal =. Shortest paths in directed planar graphs with negative lengths: A linear-space O (n log 2 n)-time algorithm , year =

  76. [85]

    Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form , year =

    Adam Karczmarz and Piotr Sankowski , booktitle =. Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form , year =

  77. [86]

    Sensitive Distance and Reachability Oracles for Large Batch Updates , year =

    Jan van den Brand and Thatchaphol Saranurak , booktitle =. Sensitive Distance and Reachability Oracles for Large Batch Updates , year =

  78. [87]

    Self-Adjusting Binary Search Trees , year =

    Daniel Dominic Sleator and Robert Endre Tarjan , journal =. Self-Adjusting Binary Search Trees , year =. doi:10.1145/3828.3835 , timestamp =

  79. [88]

    Scaling algorithms for approximate and exact maximum weight matching , year =

    Ran Duan and Seth Pettie and Hsin-Hao Su , journal =. Scaling algorithms for approximate and exact maximum weight matching , year =

  80. [89]

    Distributed Computing , title =

    Yehuda Afek and Anat Bremler. Distributed Computing , title =. 2002 , number =

    2002

  81. [90]

    Replacement paths via fast matrix multiplication , year =

    Weimann, Oren and Yuster, Raphael , booktitle =. Replacement paths via fast matrix multiplication , year =

  82. [91]

    Replacement paths and k simple shortest paths in unweighted directed graphs , year =

    Roditty, Liam and Zwick, Uri , journal =. Replacement paths and k simple shortest paths in unweighted directed graphs , year =

  83. [92]

    Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication , year =

    Weimann, Oren and Yuster, Raphael , journal =. Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication , year =. doi:10.1145/2438645.2438646 , issue_date =

  84. [93]

    Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation , year =

    Monika Rauch Henzinger and Valerie King , journal =. Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation , year =

  85. [94]

    Preserving Distances in Very Faulty Graphs , year =

    Greg Bodwin and Fabrizio Grandoni and Merav Parter and Virginia Vassilevska Williams , booktitle =. Preserving Distances in Very Faulty Graphs , year =

  86. [95]

    Practical Minimum Cut Algorithms , year =

    Monika Henzinger and Alexander Noe and Christian Schulz and Darren Strash , booktitle =. Practical Minimum Cut Algorithms , year =

  87. [96]

    Powers of tensors and fast matrix multiplication , year =

    Fran. Powers of tensors and fast matrix multiplication , year =. International Symposium on Symbolic and Algebraic Computation,

  88. [97]

    Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , year =

    Amir Abboud and Virginia Vassilevska Williams , booktitle =. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , year =

  89. [98]

    Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity , year =

    Jacob Holm and Kristian de Lichtenberg and Mikkel Thorup , journal =. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity , year =

  90. [99]

    Edmonds , journal =

    J. Edmonds , journal =. Paths, trees, and flowers , year =

  91. [100]

    Oracles for Distances Avoiding a Failed Node or Link , year =

    Camil Demetrescu and Mikkel Thorup and Rezaul Alam Chowdhury and Vijaya Ramachandran , journal =. Oracles for Distances Avoiding a Failed Node or Link , year =

  92. [101]

    On the k-simple shortest paths problem in weighted directed graphs , year =

    Roditty, Liam , booktitle =. On the k-simple shortest paths problem in weighted directed graphs , year =

  93. [102]

    Online Bipartite Matching with Amortized Replacements , year =

    Aaron Bernstein and Jacob Holm and Eva Rotenberg , booktitle =. Online Bipartite Matching with Amortized Replacements , year =. doi:10.1137/1.9781611975031.61 , groups =

    doi

  94. [103]

    On Graph Problems in a Semi-streaming Model , year =

    Feigenbaum, Joan and Kannan, Sampath and McGregor, Andrew and Suri, Siddharth and Zhang, Jian , journal =. On Graph Problems in a Semi-streaming Model , year =. doi:10.1016/j.tcs.2005.09.013 , issue_date =

    2005 doi

  95. [104]

    On Dynamic Shortest Paths Problems , year =

    Liam Roditty and Uri Zwick , journal =. On Dynamic Shortest Paths Problems , year =

  96. [105]

    CoRR , title =

    Rapha. CoRR , title =. 2015 , volume =

    2015

  97. [106]

    New bounds on the complexity of the shortest path problem , year =

    Fredman, Michael L , journal =. New bounds on the complexity of the shortest path problem , year =

  98. [107]

    Accepted in Annual European Symposium on Algorithms, ESA 2021 , title =

    Davide Bil. Accepted in Annual European Symposium on Algorithms, ESA 2021 , title =

    2021

  99. [108]

    Near Optimal Algorithms For The Single Source Replacement Paths Problem , year =

    Shiri Chechik and Sarel Cohen , booktitle =. Near Optimal Algorithms For The Single Source Replacement Paths Problem , year =

  100. [109]

    Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem , year =

    Shiri Chechik and Ofer Magen , booktitle =. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem , year =

  101. [110]

    2022 , address =

    Dey, Dipan and Gupta, Manoj , booktitle =. 2022 , address =. doi:10.4230/LIPIcs.ESA.2022.42 , isbn =

    2022 doi

  102. [111]

    Near Approximation of Maximum Weight Matching through Efficient Weight Reduction , year =

    Andrzej Lingas and Cui Di , booktitle =. Near Approximation of Maximum Weight Matching through Efficient Weight Reduction , year =

  103. [112]

    Multiplying matrices faster than coppersmith-winograd , year =

    Virginia Vassilevska Williams , booktitle =. Multiplying matrices faster than coppersmith-winograd , year =

  104. [113]

    Multiple Source Replacement Path Problem , year =

    Manoj Gupta and Rahul Jain and Nitiksha Modi , booktitle =. Multiple Source Replacement Path Problem , year =

  105. [114]

    Multiple Source Dual Fault Tolerant

    Manoj Gupta and Shahbaz Khan , booktitle =. Multiple Source Dual Fault Tolerant. 2017 , pages =

    2017

  106. [115]

    Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees , year =

    Davide Bil. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees , year =. 33rd Symposium on Theoretical Aspects of Computer Science,

  107. [116]

    More algorithms for all-pairs shortest paths in weighted graphs , year =

    Chan, Timothy M , booktitle =. More algorithms for all-pairs shortest paths in weighted graphs , year =

  108. [117]

    Maximum Matchings via Gaussian Elimination , year =

    Marcin Mucha and Piotr Sankowski , booktitle =. Maximum Matchings via Gaussian Elimination , year =

  109. [118]

    Matrix multiplication via arithmetic progressions , year =

    Coppersmith, Don and Winograd, Shmuel , booktitle =. Matrix multiplication via arithmetic progressions , year =

  110. [119]

    Lovasz and M.D

    L. Lovasz and M.D. Plummer , publisher =. Matching Theory , year =

  111. [120]

    Edmonds and E

    J. Edmonds and E. L. Johnson , journal =. Matching, Euler tours, and the Chinese postman , year =

  112. [121]

    Driscoll and Neil Sarnak and Daniel Dominic Sleator and Robert Endre Tarjan , journal =

    James R. Driscoll and Neil Sarnak and Daniel Dominic Sleator and Robert Endre Tarjan , journal =. Making Data Structures Persistent , year =

  113. [122]

    Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract] , year =

    Aaron Bernstein , booktitle =. Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract] , year =

  114. [123]

    Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs , year =

    Aaron Bernstein , journal =. Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs , year =. doi:10.1137/130938670 , groups =

    doi

  115. [124]

    Maintaining exact distances under multiple edge failures , year =

    Ran Duan and Hanlin Ren , booktitle =. Maintaining exact distances under multiple edge failures , year =. doi:10.1145/3519935.3520002 , timestamp =

  116. [125]

    2012 , address =

    Abhash Anand and Surender Baswana and Manoj Gupta and Sandeep Sen , booktitle =. 2012 , address =. doi:http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.257 , isbn =

    2012 doi

  117. [126]

    Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs , year =

    Abhash Anand and Surender Baswana and Manoj Gupta and Sandeep Sen , journal =. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs , year =

  118. [127]

    Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time , year =

    Manoj Gupta , booktitle =. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time , year =

  119. [128]

    Maintaining a large matching and a small vertex cover , year =

    Krzysztof Onak and Ronitt Rubinfeld , booktitle =. Maintaining a large matching and a small vertex cover , year =

  120. [129]

    Locality in Distributed Graph Algorithms , year =

    Nathan Linial , journal =. Locality in Distributed Graph Algorithms , year =. doi:10.1137/0221015 , timestamp =

    doi

  121. [130]

    Linear programming in the semi-streaming model with application to the maximum matching problem , year =

    Ahn, Kook Jin and Guha, Sudipto , journal =. Linear programming in the semi-streaming model with application to the maximum matching problem , year =

  122. [131]

    Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time , year =

    Gramoz Goranci and Monika Henzinger and Mikkel Thorup , booktitle =. Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time , year =

  123. [132]

    Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning , year =

    Monika Henzinger and Stefan Neumann , booktitle =. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning , year =

  124. [133]

    Improved upper bounds for time-space trade-offs for selection , year =

    Raman, Venkatesh and Ramnath, Sarnath , journal =. Improved upper bounds for time-space trade-offs for selection , year =

  125. [134]

    Improved Space Efficient Algorithms for BFS,

    Niranka Banerjee and Sankardeep Chakraborty and Venkatesh Raman , booktitle =. Improved Space Efficient Algorithms for BFS,. 2016 , pages =

    2016

  126. [135]

    Improved Purely Additive Fault-Tolerant Spanners , year =

    Davide Bil. Improved Purely Additive Fault-Tolerant Spanners , year =. Algorithms -

  127. [136]

    Improved Guarantees for Vertex Sparsification in Planar Graphs , year =

    Gramoz Goranci and Monika Henzinger and Pan Peng , booktitle =. Improved Guarantees for Vertex Sparsification in Planar Graphs , year =

  128. [137]

    Improved Dynamic Reachability Algorithms for Directed Graphs , year =

    Liam Roditty and Uri Zwick , journal =. Improved Dynamic Reachability Algorithms for Directed Graphs , year =

  129. [138]

    Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions , year =

    Aaron Bernstein and Liam Roditty , booktitle =. Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions , year =. doi:10.1137/1.9781611973082.104 , groups =

    doi

  130. [139]

    Improved distance sensitivity oracles with subcubic preprocessing time , year =

    Ren, Hanlin , journal =. Improved distance sensitivity oracles with subcubic preprocessing time , year =

  131. [140]

    Karger , booktitle =

    Aaron Bernstein and David R. Karger , booktitle =. Improved distance sensitivity oracles via random sampling , year =

  132. [141]

    Improved distance sensitivity oracles via fast single-source replacement paths , year =

    Grandoni, Fabrizio and Williams, Virginia Vassilevska , booktitle =. Improved distance sensitivity oracles via fast single-source replacement paths , year =

  133. [142]

    Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components , year =

    Jakub Lacki , journal =. Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components , year =

  134. [143]

    Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths , year =

    Surender Baswana and Ramesh Hariharan and Sandeep Sen , journal =. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths , year =

  135. [144]

    Improved Bounds for Online Preemptive Matching , year =

    Leah Epstein and Asaf Levin and Danny Segev and Oren Weimann , journal =. Improved Bounds for Online Preemptive Matching , year =

  136. [145]

    STACS , title =

    Leah Epstein and Asaf Levin and Juli. STACS , title =. 2010 , pages =

    2010

  137. [146]

    Improved algorithms for the k simple shortest paths and the replacement paths problems , year =

    Gotthilf, Zvi and Lewenstein, Moshe , journal =. Improved algorithms for the k simple shortest paths and the replacement paths problems , year =

  138. [147]

    Implementation and Experimental Analysis of a Dynamic Matching Algorithm and its Variations , year =

    Hemantika Nagpal , journal =. Implementation and Experimental Analysis of a Dynamic Matching Algorithm and its Variations , year =

  139. [148]

    Ullman and Mihalis Yannakakis , booktitle =

    Jeffrey D. Ullman and Mihalis Yannakakis , booktitle =. High-Probability Parallel Transitive Closure Algorithms , year =

  140. [149]

    Graph sketches: sparsification, spanners, and subgraphs , year =

    Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew , booktitle =. Graph sketches: sparsification, spanners, and subgraphs , year =

  141. [150]

    Generic Single Edge Fault Tolerant Exact Distance Oracle , year =

    Manoj Gupta and Aditi Singh , booktitle =. Generic Single Edge Fault Tolerant Exact Distance Oracle , year =

  142. [151]

    Fully dynamic randomized algorithms for graph spanners , year =

    Surender Baswana and Sumeet Khurana and Soumojit Sarkar , journal =. Fully dynamic randomized algorithms for graph spanners , year =

  143. [152]

    Fully-Dynamic Min-Cut , year =

    Mikkel Thorup , journal =. Fully-Dynamic Min-Cut , year =

  144. [153]

    Fully Dynamic Maximal Matching in

    Surender Baswana and Manoj Gupta and Sandeep Sen , journal =. Fully Dynamic Maximal Matching in. 2015 , number =. doi:10.1137/130914140 , timestamp =

    2015 doi

  145. [154]

    Fully Dynamic Matching in Bipartite Graphs , year =

    Aaron Bernstein and Cliff Stein , booktitle =. Fully Dynamic Matching in Bipartite Graphs , year =. doi:10.1007/978-3-662-47672-7_14 , groups =

    doi

  146. [155]

    , booktitle =

    Ivkovic, Zoran and Lloyd, Errol L. , booktitle =. Fully Dynamic Maintenance of Vertex Cover , year =

  147. [156]

    Fully Dynamic Biconnectivity and Transitive Closure , year =

    Monika Rauch Henzinger and Valerie King , booktitle =. Fully Dynamic Biconnectivity and Transitive Closure , year =

  148. [157]

    Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in

    Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai , booktitle =. Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in. 2017 , editor =

    2017

  149. [158]

    Fully Dynamic Algorithms For Maintaining Approximate Matching In Graphs , year =

    Abhash Anand , school =. Fully Dynamic Algorithms For Maintaining Approximate Matching In Graphs , year =

  150. [159]

    Fully Dynamic (1+ ) -Approximate Matchings , year =

    Manoj Gupta and Richard Peng , booktitle =. Fully Dynamic (1+ ) -Approximate Matchings , year =

  151. [160]

    Finding the most vital node of a shortest path , year =

    Enrico Nardelli and Guido Proietti and Peter Widmayer , journal =. Finding the most vital node of a shortest path , year =

  152. [161]

    Finding the k Shortest Paths , year =

    David Eppstein , booktitle =. Finding the k Shortest Paths , year =

  153. [162]

    Finding Graph Matchings in Data Streams , year =

    Andrew McGregor , booktitle =. Finding Graph Matchings in Data Streams , year =

  154. [163]

    Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time , year =

    Monika Henzinger and Sebastian Krinninger and Veronika Loitzenbauer , booktitle =. Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time , year =

  155. [164]

    Fault tolerant subgraph for single source reachability: generic and optimal , year =

    Surender Baswana and Keerti Choudhary and Liam Roditty , booktitle =. Fault tolerant subgraph for single source reachability: generic and optimal , year =

  156. [165]

    Fault Tolerant Spanners for General Graphs , year =

    Shiri Chechik and Michael Langberg and David Peleg and Liam Roditty , journal =. Fault Tolerant Spanners for General Graphs , year =

  157. [166]

    Fault-tolerant spanners: better and simpler , year =

    Michael Dinitz and Robert Krauthgamer , booktitle =. Fault-tolerant spanners: better and simpler , year =

  158. [167]

    Fault Tolerant Reachability for Directed Graphs , year =

    Surender Baswana and Keerti Choudhary and Liam Roditty , booktitle =. Fault Tolerant Reachability for Directed Graphs , year =

  159. [168]

    Fault-Tolerant Approximate Shortest-Path Trees , year =

    Davide Bil. Fault-Tolerant Approximate Shortest-Path Trees , year =. Algorithms -

  160. [169]

    Fault Tolerant Approximate

    Merav Parter and David Peleg , booktitle =. Fault Tolerant Approximate. 2014 , pages =

    2014

  161. [170]

    Fault tolerant additive and (

    Gilad Braunschvig and Shiri Chechik and David Peleg and Adam Sealfon , journal =. Fault tolerant additive and (. 2015 , pages =

    2015

  162. [171]

    Gabow and Robert Endre Tarjan , journal =

    Harold N. Gabow and Robert Endre Tarjan , journal =. Faster Scaling Algorithms for General Graph-Matching Problems , year =

  163. [172]

    Faster replacement paths and distance sensitivity oracles , year =

    Grandoni, Fabrizio and Williams, Virginia Vassilevska , journal =. Faster replacement paths and distance sensitivity oracles , year =

  164. [173]

    Faster replacement paths , year =

    Williams, Virginia Vassilevska , booktitle =. Faster replacement paths , year =

  165. [174]

    Faster Fully Dynamic Matchings with Small Approximation Ratios , year =

    Aaron Bernstein and Cliff Stein , booktitle =. Faster Fully Dynamic Matchings with Small Approximation Ratios , year =. doi:10.1137/1.9781611974331.ch50 , groups =

    doi

  166. [175]

    Faster dynamic matchings and vertex connectivity , year =

    Piotr Sankowski , booktitle =. Faster dynamic matchings and vertex connectivity , year =

  167. [176]

    Faster all-pairs shortest paths via circuit complexity , year =

    Williams, Ryan , booktitle =. Faster all-pairs shortest paths via circuit complexity , year =

  168. [177]

    Faster, space-efficient selection algorithms in read-only memory for integers , year =

    Chan, Timothy M and Munro, J Ian and Raman, Venkatesh , booktitle =. Faster, space-efficient selection algorithms in read-only memory for integers , year =

  169. [178]

    Efficient Oracles and Routing Schemes for Replacement Paths , year =

    Davide Bil. Efficient Oracles and Routing Schemes for Replacement Paths , year =. 35th Symposium on Theoretical Aspects of Computer Science,

  170. [179]

    Efficient algorithms for maximum weight matchings in general graphs with small edge weights , year =

    Chien-Chung Huang and Telikepalli Kavitha , booktitle =. Efficient algorithms for maximum weight matchings in general graphs with small edge weights , year =

  171. [180]

    Karlin and Kurt Mehlhorn and Friedhelm

    Martin Dietzfelbinger and Anna R. Karlin and Kurt Mehlhorn and Friedhelm. Dynamic Perfect Hashing: Upper and Lower Bounds , year =

  172. [181]

    Kapron and Valerie King and Ben Mountjoy , booktitle =

    Bruce M. Kapron and Valerie King and Ben Mountjoy , booktitle =. Dynamic graph connectivity in polylogarithmic worst case time , year =

  173. [182]

    Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs , year =

    Liam Roditty and Uri Zwick , journal =. Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs , year =

  174. [183]

    Dynamic Algorithms for Graph Coloring , year =

    Sayan Bhattacharya and Deeparnab Chakrabarty and Monika Henzinger and Danupon Nanongkai , booktitle =. Dynamic Algorithms for Graph Coloring , year =

  175. [184]

    Surender Baswana and Shreejit Ray Chaudhury and Keerti Choudhary and Shahbaz Khan , booktitle =. Dynamic. 2016 , pages =

    2016

  176. [185]

    Dual Failure Resilient

    Merav Parter , booktitle =. Dual Failure Resilient. 2015 , pages =

    2015

  177. [186]

    Dual-failure distance and connectivity oracles , year =

    Ran Duan and Seth Pettie , booktitle =. Dual-failure distance and connectivity oracles , year =

  178. [187]

    and Patt-Shamir, B

    Lotker, Z. and Patt-Shamir, B. and Rosen, A. , booktitle =. 2007 , organization =

    2007

  179. [188]

    Distance sensitivity oracles with subcubic preprocessing time and fast query time , year =

    Chechik, Shiri and Cohen, Sarel , booktitle =. Distance sensitivity oracles with subcubic preprocessing time and fast query time , year =

  180. [189]

    Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs , year =

    Aaron Bernstein , booktitle =. Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs , year =. doi:10.4230/LIPIcs.ICALP.2017.44 , groups =

    2017 doi

  181. [190]

    Italiano , booktitle =

    Sayan Bhattacharya and Monika Henzinger and Giuseppe F. Italiano , booktitle =. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching , year =

  182. [191]

    Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in

    Sayan Bhattacharya and Deeparnab Chakrabarty and Monika Henzinger , booktitle =. Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in. 2017 , editor =

    2017

  183. [192]

    Italiano , booktitle =

    Sayan Bhattacharya and Monika Henzinger and Giuseppe F. Italiano , booktitle =. Design of Dynamic Algorithms via Primal-Dual Method , year =

  184. [193]

    Decremental maintenance of strongly connected components , year =

    Liam Roditty , booktitle =. Decremental maintenance of strongly connected components , year =

  185. [194]

    Decremental Approximate-APSP in Directed Graphs , year =

    Aaron Bernstein , booktitle =. Decremental Approximate-APSP in Directed Graphs , year =. doi:10.1007/978-1-4939-2864-4_564 , groups =

    doi

  186. [195]

    , journal =

    Frederickson, G. , journal =. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications , year =

  187. [196]

    Data structures and network algorithms , year =

    Robert Endre Tarjan , publisher =. Data structures and network algorithms , year =

  188. [197]

    Cuckoo hashing , year =

    Rasmus Pagh and Flemming Friche Rodler , journal =. Cuckoo hashing , year =

  189. [198]

    Mirrokni and Cliff Stein , journal =

    Sepehr Assadi and MohammadHossein Bateni and Aaron Bernstein and Vahab S. Mirrokni and Cliff Stein , journal =. Coresets Meet. 2017 , volume =. arXiv , bibsource =:1711.03076 , groups =

    2017 arXiv

  190. [199]

    Constructing a Distance Sensitivity Oracle in

    Yong Gu and Hanlin Ren , booktitle =. Constructing a Distance Sensitivity Oracle in. 2021 , editor =

    2021

  191. [200]

    Conditional Hardness for Sensitivity Problems , year =

    Monika Henzinger and Andrea Lincoln and Stefan Neumann and Virginia Vassilevska Williams , booktitle =. Conditional Hardness for Sensitivity Problems , year =

  192. [201]

    Compact and Fast Sensitivity Oracles for Single-Source Distances , year =

    Davide Bil. Compact and Fast Sensitivity Oracles for Single-Source Distances , year =. 24th Annual European Symposium on Algorithms,

  193. [202]

    Lawler , publisher =

    E. Lawler , publisher =. Combinatorial Optimization: Networks and Matroids , year =

  194. [203]

    Combinatorial optimization: algorithms and complexity , year =

    Christos Papadimitriou and Kenneth Steiglitz , publisher =. Combinatorial optimization: algorithms and complexity , year =

  195. [204]

    Average Case Analysis of Dynamic Graph Algorithms , year =

    David Alberts and Monika Rauch Henzinger , booktitle =. Average Case Analysis of Dynamic Graph Algorithms , year =

  196. [205]

    Average-Case Analysis of Algorithms for Matchings and Related Problems , year =

    Rajeev Motwani , journal =. Average-Case Analysis of Algorithms for Matchings and Related Problems , year =

  197. [206]

    A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , booktitle =. A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths , year =

  198. [207]

    A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths , year =

    Zwick, Uri , booktitle =. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths , year =

  199. [208]

    and Sanders, P

    Pettie, S. and Sanders, P. , journal =. 2004 , number =

    2004

  200. [209]

    A Simple Parallel Algorithm for the Maximal Independent Set Problem , year =

    Luby, M , booktitle =. A Simple Parallel Algorithm for the Maximal Independent Set Problem , year =. doi:10.1145/22145.22146 , isbn =

  201. [210]

    and Hougardy, S

    Drake, D.E. and Hougardy, S. , journal =. 2003 , number =

    2003

  202. [211]

    Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms , year =

    Michal Parnas and Dana Ron , journal =. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms , year =

  203. [212]

    Approximating Maximum Weight Matching in Near-Linear Time , year =

    Duan, Ran and Pettie, Seth , booktitle =. Approximating Maximum Weight Matching in Near-Linear Time , year =. doi:10.1109/FOCS.2010.70 , isbn =

    2010 doi

  204. [213]

    Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs , year =

    Baswana, Surender and Khanna, Neelesh , journal =. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs , year =

  205. [214]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , title =

    Bil. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , title =. 2023 , pages =

    2023

  206. [215]

    An On-Line Edge-Deletion Problem , year =

    Shimon Even and Yossi Shiloach , journal =. An On-Line Edge-Deletion Problem , year =

  207. [216]

    and Vazirani, V.V

    Micali, S. and Vazirani, V.V. , booktitle =. 1980 , organization =

    1980

  208. [217]

    An O (n3loglogn/logn) time algorithm for the all-pairs shortest path problem , year =

    Takaoka, Tadao , journal =. An O (n3loglogn/logn) time algorithm for the all-pairs shortest path problem , year =

  209. [218]

    An O (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path , year =

    Han, Yijie , journal =. An O (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path , year =

  210. [219]

    Hopcroft and Richard M

    John E. Hopcroft and Richard M. Karp , journal =. An n^. 1973 , number =

    1973

  211. [220]

    A nearly optimal oracle for avoiding failed vertices and edges , year =

    Bernstein, Aaron and Karger, David , booktitle =. A nearly optimal oracle for avoiding failed vertices and edges , year =

  212. [221]

    A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs , year =

    Bernstein, Aaron , booktitle =. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs , year =

  213. [222]

    A near-linear-time algorithm for computing replacement paths in planar directed graphs , year =

    Emek, Yuval and Peleg, David and Roditty, Liam , journal =. A near-linear-time algorithm for computing replacement paths in planar directed graphs , year =

  214. [223]

    Analyzing graph structure via linear measurements , year =

    Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew , booktitle =. Analyzing graph structure via linear measurements , year =

  215. [224]

    An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths , year =

    Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai , journal =. An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths , year =. arXiv , bibsource =:1504.07056 , url =

    arXiv

  216. [225]

    A more efficient algorithm for the min-plus multiplication , year =

    Dobosiewicz, Wlodzimierz , journal =. A more efficient algorithm for the min-plus multiplication , year =

  217. [226]

    All-pairs shortest paths with real weights in O (n 3/log n) time , year =

    Chan, Timothy M , journal =. All-pairs shortest paths with real weights in O (n 3/log n) time , year =

  218. [227]

    A faster algorithm for the all-pairs shortest path problem and its application , year =

    Takaoka, Tadao , booktitle =. A faster algorithm for the all-pairs shortest path problem and its application , year =

  219. [228]

    Alon, Noga and Babai, L\'. J. Algorithms , title =. 1986 , issn =. doi:10.1016/0196-6774(86)90019-2 , issue_date =

    1986 doi

  220. [229]

    A Fast Algorithm for Finding Dominators in a Flowgraph , year =

    Thomas Lengauer and Robert Endre Tarjan , journal =. A Fast Algorithm for Finding Dominators in a Flowgraph , year =

  221. [230]

    A Data Structure for Dynamic Trees , year =

    Daniel Dominic Sleator and Robert Endre Tarjan , journal =. A Data Structure for Dynamic Trees , year =

  222. [231]

    2017 , pages =

    Shiri Chechik and Sarel Cohen and Amos Fiat and Haim Kaplan , booktitle =. 2017 , pages =

    2017

  223. [232]

    Nearly Optimal Fault Tolerant Distance Oracle , year =

    Dipan Dey and Manoj Gupta , booktitle =. Nearly Optimal Fault Tolerant Distance Oracle , year =. doi:10.1145/3618260.3649697 , timestamp =

  224. [233]

    Complexity Term Balancer

    Brand, Jan van den. Complexity Term Balancer

  225. [234]

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

    Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  226. [235]

    Uri Zwick , title =. J. 2002 , url =. doi:10.1145/567112.567114 , timestamp =

    2002

  227. [237]

    2025 , volume =

    Gupta, Manoj , booktitle =. 2025 , volume =. doi:10.1109/FOCS63196.2025.00065 , url =

    2025

  228. [238]

    SIAM Journal on Computing , volume =

    Baswana, Surender and Kavitha, Telikepalli , title =. SIAM Journal on Computing , volume =. 2010 , doi =. https://doi.org/10.1137/080737174 , abstract =

    2010 doi

  229. [239]

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

    Patrascu, Mihai and Roditty, Liam , title =. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science , pages =. 2010 , isbn =. doi:10.1109/FOCS.2010.83 , abstract =

    2010 doi

  230. [240]

    Faster Approximation of Distances in Graphs

    Berman, Piotr and Kasiviswanathan, Shiva Prasad. Faster Approximation of Distances in Graphs. Algorithms and Data Structures. 2007

    2007

  231. [241]

    Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science , pages =

    Baswana, Surender and Kavitha, Telikepalli , title =. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2006 , isbn =. doi:10.1109/FOCS.2006.29 , abstract =

    2006 doi

  232. [242]

    43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) , pages =

    Sommer, Christian , title =. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.ICALP.2016.55 , annote =

    2016 doi

  233. [243]

    Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures , pages =

    Thorup, Mikkel and Zwick, Uri , title =. Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures , pages =. 2001 , isbn =. doi:10.1145/378580.378581 , abstract =

    2001

  234. [244]

    39th International Symposium on Distributed Computing (DISC 2025) , pages =

    Kadria, Avi and Roditty, Liam , title =. 39th International Symposium on Distributed Computing (DISC 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.DISC.2025.38 , annote =

    2025 doi

Pith tools

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