Pith. sign in

REVIEW 3 major objections 4 minor 32 references

Undirected 3-Fault Replacement Path in Nearly Cubic Time

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

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

Pith's one-line read The paper claims that undirected 3-fault replacement paths can be computed deterministically in near-cubic time, nearly matching the cubic output size.

desk verdict Good incremental DSO and a clean lower bound, but the main 3FRP theorem rests on an unsupported interval-shrinking claim in Lemma 7.11. read the letter →

arxiv 2411.18312 v1 pith:PEIXHQER submitted 2024-11-27 cs.DS

Shucheng Chi , Ran Duan , Benyu Wang , Tianle Xie This is my paper · ORCID
classification cs.DS MSC 68Q2505C8568W40
keywords f-faultreplacementpathdistancesensitivityoracleincrementalDSOofflinedynamicundirectedweightedgraphsAPSP-hardnesssingle-sourcenear-cubictime
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 claims that the 3-fault replacement path problem in undirected, real-weighted graphs can be solved deterministically in $\tilde{O}(n^3)$ time for $n$ vertices. The output of the problem has $\Theta(n^3)$ distances, so the running time would be optimal up to polylogarithmic factors. If the main theorem is correct, then for every fixed $f \ge 3$ edge failures, the $f$-fault version in undirected graphs can be solved in $\tilde{O}(n^f)$ time, again nearly matching output size. The paper also gives a 2-fault single-source replacement path algorithm in $\tilde{O}(n^3)$ time and proves a conditional lower bound showing that undirected 2FRP has no truly subcubic algorithm under the APSP-hardness conjecture.

What carries the argument

The load-bearing mechanism is an incremental distance sensitivity oracle that, after each edge insertion, maintains for every pair $u,v$ the shortest path tree, an LCA structure, and stored detours $\omega_{G-(u\oplus i)(v\ominus j)}(u,v)$ for intervals whose offsets from $u$ and $v$ are powers of two. Detours are kept in proper form, meaning a shortest path, one edge, and another shortest path, so they can be transformed and compared in $\tilde{O}(1)$ time. Inserting an edge $e$ updates all affected detours through a six-case analysis of where the new shortest path diverges and converges relative to the queried interval. The second ingredient is a binary range tree on $st$: two failed edges on $st$ are separated at some level of this tree, and the replacement distance is the minimum of four DSO queries on graphs that keep only the left or right half of the interval. Three failed edges on $st$ are handled by range-to-range oracles together with a staged search in which the candidate edge set $D \cap (\pi_1 \cap \cdots \cap \pi_i)$ shrinks by a constant factor at each stage.

What would settle it

Run the described algorithm on all undirected weighted graphs up to seven vertices, including graphs with deliberately tied shortest paths, and compare every reported $\pi_{G-\{d_1,d_2,d_3\}}(s,t)$ against brute-force deletion of all edge triples; any mismatch in such a small graph would show the uniqueness assumption cannot simply be dropped. Separately, timing the worst-case edge insertion cases from Section 4.3.1 would test the claimed $\tilde{O}(n^2)$ update bound.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1.1, is that every replacement distance $|\pi_{G-\{d_1,d_2,d_3\}}(s,t)|$ for all triples of failed edges can be produced in $\tilde{O}(n^3)$ time. The argument splits by how many of the failed edges lie on the original shortest path $st$: one failed edge is handled through an incremental 1-failure distance sensitivity oracle, two failed edges reduce to a constant number of DSO queries over a binary partition of $st$, and three failed edges are answered by range-tree oracles plus a shrinking-interval search that keeps the amortized cost per triple constant. The paper further shows that, assuming the APSP conjecture, no truly subcubic algorithm for undirected 2FRP exists, and that 2-fault single-source replacement paths can be solved in $\tilde{O}(n^3)$ time.

Load-bearing premise

The paper assumes every subgraph has unique shortest paths, and all structural lemmas and update-case arguments rely on that uniqueness; without a deterministic tie-breaking scheme, the stated deterministic bound is not fully supported.

Editorial extensions

If this is right

  • For every fixed $f \ge 3$, $f$-fault replacement paths in undirected graphs can be solved in $\tilde{O}(n^f)$ time, which is within polylogarithmic factors of the $\Theta(n^f)$ output size.
  • The 2-fault single-source replacement path problem in undirected graphs can be solved in $\tilde{O}(n^3)$ time, and the extension gives $\tilde{O}(n^{f+1})$ time for all $f \ge 2$.
  • Assuming the APSP conjecture, undirected 2FRP cannot be solved in truly subcubic time, so the cubic barrier for two edge faults is conditionally optimal.
  • The incremental DSO and the offline-dynamic conversion are reusable tools: a 1-failure DSO with $\tilde{O}(n^3)$ preprocessing, $\tilde{O}(n^2)$ worst-case update time, $\tilde{O}(n^2)$ space, and $\tilde{O}(1)$ query time.

Reading between the lines

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

  • A natural next target is whether the same incremental-DSO template extends to directed graphs, but the paper's structural lemmas use undirectedness heavily, so directed 3FRP would require new arguments.
  • If the deterministic tie-breaking gap is closed, the framework would give deterministic offline dynamic distance sensitivity oracles for other distance queries under edge insertions and deletions with total near-cubic work.
  • The 2FRP hardness gadget encodes all-pairs distances using zero-weight paths and matchings, which suggests that any improvement below cubic for two faults in undirected graphs would refute the APSP conjecture rather than merely improve on this algorithm.
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 / 4 minor

Summary. The paper claims a deterministic O~(n^3)-time algorithm for undirected 3FRP in real-weighted graphs, together with extensions to fFRP for all f >= 3 and to 2-fault single-source replacement paths, plus an APSP-hardness result for undirected 2FRP. The main technical contribution is an incremental 1-failure distance sensitivity oracle with O~(n^2) worst-case update time, which is then converted into an offline fully dynamic DSO via a proposed binary range tree reduction. The algorithm splits the 3FRP query into cases according to how many failed edges lie on the original s-t shortest path, using the incremental DSO, a binary partition of the shortest path, and a range-tree oracle for snake paths. The hardness reduction for 2FRP is self-contained and reduces APSP to 2FRP by attaching zero-weight paths and weighted matchings.

Significance. If the main theorem is correct, it closes the undirected 3FRP gap and gives almost optimal O~(n^f) algorithms for all f >= 3, since the output size is Theta(n^f). The incremental DSO with O~(n^2) update time is a potentially reusable primitive, and the offline dynamic DSO reduction, if made fully rigorous, would be a useful tool beyond this paper. The 2FRP hardness reduction is clean and convincing. The paper is ambitious and contains several genuinely useful constructions and reductions. However, a number of load-bearing points are not sufficiently supported as written, so the central claim cannot currently be regarded as established.

major comments (3)
  1. [Section 2.1, Theorem 1.1] The paper states that all algorithms are deterministic, but the unique shortest path assumption is justified only by adding small random variables to the edge weights ([10]). This is a genuine mismatch: the divergence/convergence arguments, Theorem 2.1, Theorem 2.2, and the weak-point arguments in Section 4 all rely on uniqueness of shortest paths in every subgraph. If the tie-breaking is randomized, the theorem should state a randomized bound; if determinism is claimed, a deterministic symbolic tie-breaking scheme must be specified and proved to preserve the distances and the structural lemmas. As written, the deterministic guarantee of Theorem 1.1 is not supported by the stated assumptions.
  2. [Section 7.2, Lemma 7.11] The interval-shrinking proof is not sufficient. In Stage i the proof asserts that F cap (E(i-1)_1 union E(i-1)_2) consists of at most two intervals because "there is at least an edge between E(i-1)_1 and E(i-1)_2 that is not in F". This premise is not proved: e_i is the middle edge of E(i-1)_1 and lies inside one of the two current components, not necessarily between them, and the proof does not establish an invariant that the two components are separated by some edge that every subsequent pi_j avoids. If that separating edge is not identified, a single interval of F could intersect both E(i-1)_1 and E(i-1)_2 while another interval of F contributes a third piece, breaking the two-interval bookkeeping. The bound S(i+1) <= 5/8 S(i) depends critically on the two-interval claim, and hence the O(log n) stage bound for each (d1,d3) pair, and with it Theorem 7.1, is not established. This step needs either a rigorous invariant or a different shrinking argument.
  3. [Section 2.5, Theorem 2.5] The proof of the offline dynamic DSO construction does not justify the claimed O~(n^3) total time. In the binary range tree, moving from a parent node to a child adds all edges that are present throughout the child interval but not throughout the parent interval; across the whole tree the total number of such edge insertions can be Omega(m log T) = Omega(n^2 log n), and each incremental DSO update costs Omega~(n^2), giving Omega~(n^4) rather than O~(n^3). The proof of Theorem 2.5 should either be replaced by a correct invocation of the Peng-Rubinstein reduction (Theorem 2.4) with explicit per-update accounting, or the statement should be proved with a different argument. Since Sections 5, 6 and 9 explicitly rely on Theorem 2.5, this is a load-bearing issue.
minor comments (4)
  1. [Section 6.4, proof of Theorem 6.13] In the displayed lower bound for the fourth value, both terms in the first minimum are written as pi_{Hi,1-...}; the intended expression from Lemma 6.11 is a minimum over Hi,0-d1-d3 and Hi,1-d2-d3, so the subscripts should be corrected.
  2. [Section 9, correctness proof] The case where both d1 and d2 lie on the shortest path tree but the queried vertex t is not in the subtree of the first failed edge is not explicitly discussed; the argument should state that such a failed edge is not on pi(s,t) and hence does not affect the distance.
  3. [Section 4.3] The update algorithm states that shortest path trees are reconstructed after inserting e, but it does not specify how this is done within the O~(n^2) update bound; the intended method via checking min{old distances} for every pair should be stated explicitly so the time bound is verifiable.
  4. [Section 6.1] The notation d^+_1 appears in the proof of Lemma 6.2 where d^+_2 is intended; this typo makes the displayed path construction slightly confusing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 3FRP result is derived from prior published DSOs, binary-partition tools, and explicit case analyses rather than from the theorem being proved.

full rationale

The paper contains no fitted parameters and no quantity that is defined in terms of the claimed output. The central derivation chain is: build an incremental 1-failure DSO (Section 4), convert it to an offline dynamic DSO via the Peng--Rubinstein reduction and a self-contained binary-range-tree proof (Theorem 2.5), then use the DSO plus a graph H gadget to answer 3FRP queries in the cases of one, two, or three failed edges on the original shortest path (Sections 5--7). The equalities in Lemmas 5.2, 6.2, and 6.4--6.12 are proved by explicit two-directional inequalities between a shortest path in the auxiliary graph and the intended replacement path in G; they do not assume the value being computed. The incremental DSO update rules (Section 4.3) express each new detour as a minimum of old stored detours and paths through the inserted edge, with the correctness shown by a case analysis over relative positions of the divergence, convergence, and inserted edge. The only author-overlap citation is Duan--Pettie [17], whose binary-partition structure is adapted in Section 6; however, the paper defines and uses that structure as a published algorithmic tool, and the correctness of the 3FRP reduction does not rest on an unverified claim imported solely from the self-citation. The unique-shortest-path assumption (Section 2.1) is a stated assumption with a suggested random tie-breaking device; this is a determinism/correctness caveat rather than a circular step. The suspected flaw in Lemma 7.11's interval-shrinking argument is a proof gap about the number of intersection intervals, not a reduction of the theorem to its own inputs. Overall, the derivation is self-contained given the cited external DSO and reduction results, so the circularity score is 0.

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

The central claim rests on standard shortest-path assumptions plus the APSP-hardness conjecture for the lower bound; no fitted parameters or invented entities are introduced.

assumptions (4)
  • domain assumption Unique shortest path assumption
    Section 2.1. All lemmas on divergence/convergence points and replacement path structure require unique shortest paths; the paper proposes random tie-breaking, which conflicts with the deterministic claim.
  • domain assumption APSP-hardness conjecture
    Section 8 lower bound assumes APSP cannot be solved in O(n^{3-epsilon}) time.
  • standard math Path concatenation structure (Theorem 2.2 from [7])
    fault replacement paths can be partitioned into f+1 shortest subpaths interleaved with f edges; used throughout Sections 4-7.
  • domain assumption Non-negative edge weights
    Dijkstra-based algorithms and shortest path arguments assume non-negative weights; not stated explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Undirected 3-Fault Replacement Path in Nearly Cubic Time." pith.science (2026). https://pith.science/paper/PEIXHQER

@misc{pith2026241118312,
  author       = {Pith},
  title        = {Pith review of: Undirected 3-Fault Replacement Path in Nearly Cubic Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PEIXHQER}},
  note         = {Machine review of arXiv:2411.18312}
}
abstract

Given a graph $G=(V,E)$ and two vertices $s,t\in V$, the $f$-fault replacement path ($f$FRP) problem computes for every set of edges $F$ where $|F|\leq f$, the distance from $s$ to $t$ when edges in $F$ fail. A recent result shows that 2FRP in directed graphs can be solved in $\tilde{O}(n^3)$ time [arXiv:2209.07016]. In this paper, we show a 3FRP algorithm in deterministic $\tilde{O}(n^3)$ time for undirected weighted graphs, which almost matches the size of the output. This implies that $f$FRP in undirected graphs can be solved in almost optimal $\tilde{O}(n^f)$ time for all $f\geq 3$. To construct our 3FRP algorithm, we introduce an incremental distance sensitivity oracle (DSO) with $\tilde{O}(n^2)$ worst-case update time, while preprocessing time, space, and query time are still $\tilde{O}(n^3)$, $\tilde{O}(n^2)$ and $\tilde{O}(1)$, respectively, which match the static DSO [Bernstein and Karger 2009]. Here in a DSO, we can preprocess a graph so that the distance between any pair of vertices given any failed edge can be answered efficiently. From the recent result in [arXiv:2211.05178], we can obtain an offline dynamic DSO from the incremental worst-case DSO, which makes the construction of our 3FRP algorithm more convenient. By the offline dynamic DSO, we can also construct a 2-fault single-source replacement path (2-fault SSRP) algorithm in $\tilde{O}(n^3)$ time, that is, from a given vertex $s$, we want to find the distance to any vertex $t$ when any pair of edges fail. Thus the $\tilde{O}(n^3)$ time complexity for 2-fault SSRP is also almost optimal. Now we know that in undirected graphs 1FRP can be solved in $\tilde{O}(m)$ time [Nardelli, Proietti, Widmayer 2001], and 2FRP and 3FRP in undirected graphs can be solved in $\tilde{O}(n^3)$ time. In this paper, we also show that a truly subcubic algorithm for 2FRP in undirected graphs does not exist under APSP-hardness conjecture.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 31 canonical work pages

  1. [10]

    Italiano

    Camil Demetrescu and Giuseppe F. Italiano. A new approa ch to dynamic all pairs shortest paths. J. ACM, 51(6):968–992, nov 2004

    work page 2004

  2. [1]

    More asymmetry yields faster matrix multiplication, 2024

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yi nzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication, 2024

    work page 2024

  3. [2]

    Deterministi c combinatorial replacement paths and dis- tance sensitivity oracles

    Noga Alon, Shiri Chechik, and Sarel Cohen. Deterministi c combinatorial replacement paths and dis- tance sensitivity oracles. In International Colloquium on Automata, Languages and Progr amming, 2019

    work page 2019

  4. [3]

    Bender and Martín Farach-Colton

    Michael A. Bender and Martín Farach-Colton. The LCA prob lem revisited. In Gaston H. Gonnet and Alfredo Viola, editors, LATIN 2000: Theoretical Informatics , pages 88–94, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg

    work page 2000

  5. [4]

    Improved distance sen sitivity oracles via random sampling

    Aaron Bernstein and David Karger. Improved distance sen sitivity oracles via random sampling. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, page 34–43, USA, 2008. Society for Industrial and Applied Ma thematics

    work page 2008

  6. [5]

    A nearly optimal oracl e for avoiding failed vertices and edges

    Aaron Bernstein and David Karger. A nearly optimal oracl e for avoiding failed vertices and edges. In Proceedings of the Forty-First Annual ACM Symposium on Theo ry of Computing , STOC ’09, page 101–110, New Y ork, NY, USA, 2009. Association for Computing Machinery

    work page 2009

  7. [6]

    Preserving Distances in Very Faulty Graphs

    Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virgi nia Vassilevska Williams. Preserving dis- tances in very faulty graphs. CoRR, abs/1703.10293, 2017

    work page Pith review arXiv 2017

  8. [7]

    Restoration by path concatenation: fast recovery of MPLS paths

    Anat Bremler-Barr, Y ehuda Afek, Haim Kaplan, Edith Cohe n, and Michael John Merritt. Restoration by path concatenation: fast recovery of MPLS paths. ACM, 2001

    work page 2001

Show all 32 references
  1. [8]

    Near optimal algorithms f or the single source replacement paths prob- lem

    Shiri Chechik and Sarel Cohen. Near optimal algorithms f or the single source replacement paths prob- lem. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on D iscrete Algorithms, SODA ’19, page 2090–2109, USA, 2019. Society for Industrial and A pplied Mathematics

    2019

  2. [9]

    Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem

    Shiri Chechik and Ofer Magen. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Collo- quium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibni...

    2020

  3. [11]

    Oracles for distances avoiding a failed node or link

    Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhur y, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37:1299–1318, 2008

    2008

  4. [12]

    Near Optimal Algorithm for Fa ult Tolerant Distance Oracle and Single Source Replacement Path Problem

    Dipan Dey and Manoj Gupta. Near Optimal Algorithm for Fa ult Tolerant Distance Oracle and Single Source Replacement Path Problem. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms (ESA 2022) , volume 24...

    2022

  5. [13]

    Nearly optimal fault toleran t distance oracle

    Dipan Dey and Manoj Gupta. Nearly optimal fault toleran t distance oracle. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 944–955, New Y ork, NY, USA,

    2024

  6. [14]

    E. W . Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959

    1959

  7. [15]

    R. Duan, J. Mao, X. Shu, and L. Yin. A randomized algorith m for single-source shortest path on undirected real-weighted graphs. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 484–492, Los Alamitos, CA, USA, nov 2023. IEEE Comput er Society

    2023

  8. [16]

    R. Duan, H. Wu, and R. Zhou. Faster matrix multiplicatio n via asymmetric hashing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2129–2138, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society

    2023

  9. [17]

    Dual-failure distance and con nectivity oracles

    Ran Duan and Seth Pettie. Dual-failure distance and con nectivity oracles. In Proceedings of the Twen- tieth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’09, page 506–515, USA, 2009. Society for Industrial and Applied Mathematics

    2009

  10. [18]

    Maintaining exact distances un der multiple edge failures

    Ran Duan and Hanlin Ren. Maintaining exact distances un der multiple edge failures. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computin g, STOC 2022, page 1093–1101, New Y ork, NY, USA, 2022. Association for Computing Machinery

    2022

  11. [19]

    Improved distance sensitivi ty oracles via tree partitioning

    Ran Duan and Tianyi Zhang. Improved distance sensitivi ty oracles via tree partitioning. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors,Algorithms and Data Structures, pages 349–360, Cham, 2017. Springer International Publishing

    2017

  12. [20]

    Improved algorithm s for the k simple shortest paths and the re- placement paths problems

    Zvi Gotthilf and Moshe Lewenstein. Improved algorithm s for the k simple shortest paths and the re- placement paths problems. Information Processing Letters, 109(7):352–355, 2009

    2009

  13. [21]

    Improved distance sensitivity oracles via fast single-source replacement paths

    Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 748–757, 2012

    2012

  14. [22]

    Faster replacement paths and distance sensitivity oracles

    Fabrizio Grandoni and Virginia Vassilevska Williams. Faster replacement paths and distance sensitivity oracles. ACM Trans. Algorithms, 16(1), dec 2019. 38

    2019

  15. [23]

    Constructing a Distance Sensiti vity Oracle in O(n2.5794M ) Time

    Y ong Gu and Hanlin Ren. Constructing a Distance Sensiti vity Oracle in O(n2.5794M ) Time. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Pr...

    2021

  16. [24]

    Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

    Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, and Yinzhan Xu. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. I n Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and P...

    2021

  17. [25]

    A faster computation of the most vital edge of a shortest path

    Enrico Nardelli, Guido Proietti, and Peter Widmayer. A faster computation of the most vital edge of a shortest path. Information Processing Letters, 79(2):81–85, 2001

    2001

  18. [26]

    Fully-dynamic-to- incremental reductions with known deletion order (e.g

    Binghui Peng and Aviad Rubinstein. Fully-dynamic-to- incremental reductions with known deletion order (e.g. sliding window). In Symposium on Simplicity in Algorithms (SOSA), pages 261–271. SIAM, 2023

    2023

  19. [27]

    Improved distance sensitivity oracles wit h subcubic preprocessing time

    Hanlin Ren. Improved distance sensitivity oracles wit h subcubic preprocessing time. Journal of Com- puter and System Sciences, 123:159–170, 2022

    2022

  20. [28]

    New bounds for matrix multiplication: from alpha to omega

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In Proceedings of SODA ’24, pages 3792–3835, 01 2024

    2024

  21. [29]

    Faster all-pairs shortest paths via cir cuit complexity

    Ryan Williams. Faster all-pairs shortest paths via cir cuit complexity. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , STOC ’14, page 664–673, New Y ork, NY, USA,

  22. [30]

    Williams, E

    V . Williams, E. Woldeghebriel, and Y . Xu. Algorithms an d lower bounds for replacement paths under multiple edge failure. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer S cience (FOCS), pages 907–918, Los Alamitos, CA, USA, nov 2022. IEEE Comput er Society

    2022

  23. [31]

    Ryan Williams

    Virginia Vassilevska Williams and R. Ryan Williams. Su bcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5), aug 2018. 39

    2018

  24. [2014]

    Association for Computing Machinery

Pith tools

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