Warm-Starting All-Pairs Shortest Paths with Predictions

Adam Polak; Jonas Schmidt

arxiv: 2607.00857 · v1 · pith:SRSDLRFCnew · submitted 2026-07-01 · 💻 cs.DS

Warm-Starting All-Pairs Shortest Paths with Predictions

Adam Polak , Jonas Schmidt This is my paper

Pith reviewed 2026-07-02 04:26 UTC · model grok-4.3

classification 💻 cs.DS

keywords all-pairs shortest pathsalgorithms with predictionsfine-grained complexitylearning augmented algorithmsexact triangle problemprediction errorAPSP hypothesis

0 comments

The pith

APSP algorithm runs in O(n^{2.83} + η n) time given predictions of shortest detours for each pair.

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

The paper establishes an algorithm for All-Pairs Shortest Paths that incorporates predictions about the vertices on shortest detours. These predictions allow the computation to finish faster than the conjectured cubic time whenever the number of incorrect predictions is sufficiently small. The approach works by adapting a recent co-nondeterministic method for the Exact Triangle problem to identify and correct errors in the predictions. A reader would care because this is an initial exploration of learning-augmented methods for a core problem in fine-grained complexity theory.

Core claim

The paper shows that APSP admits an algorithm running in O(n^{2.83} + η n) time when supplied with a prediction of the shortest-detour vertex sets for each pair of vertices. Here η measures the number of pairs where this prediction does not suffice to compute and certify the shortest path lengths. The algorithm extends the co-nondeterministic Exact Triangle procedure of Chan, Vassilevska Williams, and Xu to detect mistakes in the supplied certificates and recover from them.

What carries the argument

An adaptation of the co-nondeterministic algorithm for Exact Triangle that detects and corrects mistakes in the nondeterministic certificates provided by the detour predictions.

If this is right

The runtime is subcubic as long as the prediction error η is polynomially smaller than n².
This provides the first learning-augmented algorithm for a problem whose hardness is tied to the APSP hypothesis.
The method gracefully degrades with the quality of the predictions through the linear dependence on η.

Where Pith is reading between the lines

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

If predictions can be obtained from machine learning models trained on similar graph instances, practical speedups may be possible on real data.
The same prediction-based warm-starting approach could apply to other problems with known fine-grained cubic lower bounds.
Further work might tighten the exponent 2.83 or reduce the dependence on η.

Load-bearing premise

The co-nondeterministic algorithm for Exact Triangle can be extended to detect mistakes in the prediction certificates and recover without exceeding the stated runtime bound.

What would settle it

Demonstrating that no such extension of the Exact Triangle algorithm exists that keeps the runtime at O(n^{2.83} + η n) when handling arbitrary prediction mistakes.

read the original abstract

One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors, in the worst case. We initiate the study of APSP in the paradigm of algorithms with predictions, also known as learning-augmented algorithms. We propose an APSP algorithm that takes as additional input a \emph{prediction} (e.g., given by a model learned from similar instances seen in the past) consisting of sets of vertices causing the shortest \emph{detour} for each pair of vertices. The algorithm runs in time $\mathcal{O}(n^{2.83} + \eta n)$, where $\eta$ denotes the \emph{prediction error} defined as the number of pairs of vertices for which, informally speaking, the prediction was not sufficient to compute and certify optimality of the shortest path length. This is already subcubic when the prediction error is (polynomially) smaller than its maximum possible values $n^2$, i.e., whenever the prediction is at least slightly better than terrible. We build on the co-nondeterministic algorithm for the Exact Triangle problem by Chan, Vassilevska Williams, and Xu (STOC 2023), essentially enabling this algorithm to detect mistakes in the nondeterministic certificate and recover from them. Our result constitutes the first necessary step towards designing learning-augmented algorithms for problems with known fine-grained lower bounds conditioned on the APSP Hypothesis.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper starts APSP with predictions via detour-vertex sets and claims O(n^{2.83} + ηn) time by adapting the 2023 co-nondet Exact Triangle algorithm; the adaptation is the part that needs checking.

read the letter

The one or two things to know: this paper gives the first APSP algorithm in the algorithms-with-predictions model, with a runtime O(n^{2.83} + η n) that depends on the prediction error η. It does so by extending the co-nondeterministic Exact Triangle algorithm from Chan, Vassilevska Williams, and Xu's STOC 2023 paper.

The new part is the prediction model based on sets of vertices that cause the shortest detour for each pair, plus the explicit bound that becomes subcubic as soon as η is smaller than n^2 by a polynomial factor. The paper does a good job of making the error measure simple and tying the result to the APSP hypothesis without extra assumptions.

The soft spot is in the adaptation step. The runtime comes from running the triangle algorithm on a graph where the prediction supplies the certificate, then detecting mistakes and recovering for the η bad pairs. The paper must show that this detection and recovery fits inside the co-nondeterministic framework without adding more than linear cost per error. If the recovery ends up requiring a separate expensive computation for each mistake, the bound would not hold. The abstract claims they enable detection and recovery, but the details determine whether the O(η n) term is realistic.

The math looks clean on the surface with no invented entities or free parameters. The citation to the 2023 result is appropriate since it is the base.

This paper is for researchers interested in bringing predictions into fine-grained graph algorithms. A reader who knows the APSP hypothesis and the recent triangle algorithms will get the most out of it.

It deserves a serious referee because it opens a new direction, even though the central technical extension requires careful checking in the full proof.

Referee Report

2 major / 1 minor

Summary. The paper initiates the study of All-Pairs Shortest Paths (APSP) in the learning-augmented setting. It proposes an algorithm that receives, for each pair of vertices, a prediction consisting of sets of vertices causing the shortest detour. The claimed runtime is O(n^{2.83} + η n), where η counts the pairs for which the prediction fails to compute and certify the shortest-path length. The result is obtained by extending the co-nondeterministic Exact Triangle algorithm of Chan, Vassilevska Williams, and Xu (STOC 2023) so that it can detect errors in the supplied nondeterministic certificate and recover from them.

Significance. If the central claim holds, the work supplies the first APSP algorithm whose runtime improves over the cubic barrier whenever the prediction error η is polynomially smaller than n². It demonstrates that even weak predictions suffice for a subcubic guarantee and constitutes an initial step toward learning-augmented algorithms for problems whose fine-grained hardness is conditioned on the APSP hypothesis.

major comments (2)

[Abstract / algorithm description] The manuscript asserts that the co-nondeterministic Exact Triangle procedure can be extended to detect mistakes in the nondeterministic certificate supplied by the prediction and to recover from them while preserving the O(n^{2.83}) base time plus an O(η n) recovery term. No proof sketch, pseudocode, or error analysis of this extension is supplied (see the paragraph after the runtime statement in the abstract and the description of the algorithm). Because this extension is the sole mechanism producing the stated bound, the absence of a verifiable argument renders the central claim unverifiable from the given text.
[Abstract / definition of η] The definition of the prediction error η (number of pairs for which the prediction is “not sufficient to compute and certify optimality”) is used both to state the runtime and to argue that the result is already subcubic for any η = o(n²). It is not shown that the recovery procedure for these η pairs can be performed with only linear work per pair inside the co-nondeterministic framework; any hidden super-linear factor in the matrix-multiplication exponent would invalidate the claimed bound.

minor comments (1)

The abstract refers to “sets of vertices causing the shortest detour” without a formal definition of the prediction format or of how these sets are represented as input; a precise interface should be stated early in the paper.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments point by point below and commit to revisions that supply the missing details.

read point-by-point responses

Referee: [Abstract / algorithm description] The manuscript asserts that the co-nondeterministic Exact Triangle procedure can be extended to detect mistakes in the nondeterministic certificate supplied by the prediction and to recover from them while preserving the O(n^{2.83}) base time plus an O(η n) recovery term. No proof sketch, pseudocode, or error analysis of this extension is supplied (see the paragraph after the runtime statement in the abstract and the description of the algorithm). Because this extension is the sole mechanism producing the stated bound, the absence of a verifiable argument renders the central claim unverifiable from the given text.

Authors: We agree that the current manuscript version does not contain a proof sketch, pseudocode, or error analysis for the extension of the Chan-Vassilevska Williams-Xu co-nondeterministic Exact Triangle algorithm. This omission makes the central runtime claim difficult to verify from the text alone. In the revised manuscript we will add a dedicated subsection that (i) describes the modified procedure, (ii) shows how it detects certificate errors arising from incorrect predictions, (iii) details the recovery mechanism, and (iv) proves that the base O(n^{2.83}) time is preserved while the recovery cost is bounded by O(η n). revision: yes
Referee: [Abstract / definition of η] The definition of the prediction error η (number of pairs for which the prediction is “not sufficient to compute and certify optimality”) is used both to state the runtime and to argue that the result is already subcubic for any η = o(n²). It is not shown that the recovery procedure for these η pairs can be performed with only linear work per pair inside the co-nondeterministic framework; any hidden super-linear factor in the matrix-multiplication exponent would invalidate the claimed bound.

Authors: We acknowledge that the manuscript does not explicitly demonstrate that recovery for each of the η erroneous pairs requires only O(n) work without introducing super-linear factors relative to the matrix-multiplication exponent. In the revision we will insert a precise accounting of the recovery cost inside the co-nondeterministic framework, showing that each erroneous pair can be handled with linear work and that the overall overhead remains O(η n) while preserving the O(n^{2.83}) term. revision: yes

Circularity Check

0 steps flagged

No circularity; runtime derived from external algorithm plus explicit error term

full rationale

The claimed runtime O(n^{2.83} + η n) is obtained by invoking and extending the co-nondeterministic Exact Triangle algorithm of Chan, Vassilevska Williams, and Xu (STOC 2023), an external result with different authors. η is defined directly as the number of pairs where the supplied prediction fails to certify optimality; the additional O(η n) term follows from the paper's stated recovery procedure on those pairs. No self-citations appear in the load-bearing steps, no parameters are fitted and then renamed as predictions, and no uniqueness theorems or ansatzes are imported from the authors' prior work. The derivation is therefore self-contained against the cited external benchmark and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the correctness of the Chan-Vassilevska Williams-Xu STOC 2023 co-nondeterministic algorithm for Exact Triangle as a black-box primitive; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

domain assumption The co-nondeterministic algorithm for Exact Triangle from Chan et al. (STOC 2023) is correct and can be modified to detect and recover from certificate errors supplied by an external prediction.
Invoked in the abstract as the foundation for handling prediction mistakes.

pith-pipeline@v0.9.1-grok · 5796 in / 1303 out tokens · 24993 ms · 2026-07-02T04:26:04.070977+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 17 canonical work pages

[1]

2 Ittai Abraham, Shiri Chechik, and Sebastian Krinninger

URL: https: //proceedings.mlr.press/v267/aamand25c.html. 2 Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 440–452. SIAM,

2017
[2]

3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou

doi:10.1137/1.9781611974782.28. 3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 2005–2039. SIAM,

work page doi:10.1137/1.9781611974782.28 2025
[3]

4Noga Alon and Joel H Spencer.The probabilistic method

doi:10.1137/1.9781611978322.63. 4Noga Alon and Joel H Spencer.The probabilistic method. John Wiley & Sons,

work page doi:10.1137/1.9781611978322.63
[4]

net/forum?id=AEFVa6VMu1

URL: https://openreview. net/forum?id=AEFVa6VMu1. 6 Benny Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions.SIAM Journal on Computing, 42:2008–2037,

2008
[5]

7 Xingjian Bai and Christian Coester

doi:10.1137/ 120884857. 7 Xingjian Bai and Christian Coester. Sorting with predictions. InAdvances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023,

2023
[6]

8 Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen

URL: http://papers.nips.cc/paper_files/paper/ 2023/hash/544696ef4847c903376ed6ec58f3a703-Abstract-Conference.html. 8 Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single- source shortest paths in near-linear time.J. ACM, 72(4):1–34,

2023
[7]

9 Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan

Announced at FOCS 2022.doi:10.1145/3742890. 9 Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an o(n¼) approximation for densest k-subgraph. InProceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pages 201—-210. ACM, 2010.doi:10.1145/1806689.1806719. 10 Ja...

work page doi:10.1145/3742890 2022
[8]

12 Timothy M

doi:10.1145/2840728.2840746. 12 Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Fredman’s trick meets dominance product: Fine-grained complexity of unweighted APSP, 3SUM counting, and more. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 419–432. ACM, 2023.doi:10.1145/3564246.3585237. 13 Justin Y. Ch...

work page doi:10.1145/2840728.2840746 2023
[9]

15 Eden Chlamtáč, Michael Dinitz, and Yury Makarychev

Announced at APPROX/RANDOM 2016.doi:10.1137/16M1096402. 15 Eden Chlamtáč, Michael Dinitz, and Yury Makarychev. Minimizing the union: tight approx- imations for small set bipartite vertex expansion. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 881—-899. SIAM,

work page doi:10.1137/16m1096402 2016
[10]

16 Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang

doi:10.1137/1.9781611974782.56. 16 Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster Ford-Fulkerson. InInternational Conference on Machine Learning, ICML 2023, volume 202 ofProceedings of Machine Learning Research, pages 7231–7248. PMLR,

work page doi:10.1137/1.9781611974782.56 2023
[11]

17 Sami Davies, Sergei Vassilvitskii, and Yuyan Wang

URL: https://proceedings.mlr.press/v202/davies23b.html. 17 Sami Davies, Sergei Vassilvitskii, and Yuyan Wang. Warm-starting push-relabel. InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024,

2024
[12]

18 Edsger W

URL: http://papers.nips.cc/paper_files/ paper/2024/hash/39ec972afab01e0d8ddc6834a9d12ac1-Abstract-Conference.html. 18 Edsger W. Dijkstra. A note on two problems in connexion with graphs.Numerische Mathematik, 1:269–271, 1959.doi:10.1007/BF01386390. 19 Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvit- skii. Faster matchi...

work page doi:10.1007/bf01386390 2024
[13]

20 Jon C

URL:https://proceedings.neurips.cc/paper/2021/hash/ 5616060fb8ae85d93f334e7267307664-Abstract.html. 20 Jon C. Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou. Learning- augmented k-means clustering. InInternational Conference on Learning Representations, ICLR 2022,

2021
[14]

21 Jeremy T

URL:https://openreview.net/forum?id=X8cLTHexYyY. 21 Jeremy T. Fineman. Single-source shortest paths with negative real weights in˜O(mn8/9)time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 3–14. ACM, 2024.doi:10.1145/3618260.3649614. 22 Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, and Aurelio ...

work page doi:10.1145/3618260.3649614 2024
[15]

23 Robert W

doi:10.1137/1.9781611978315.17. 23 Robert W. Floyd. Algorithm 97: Shortest path.Commun. ACM, 5(6):345,

work page doi:10.1137/1.9781611978315.17
[16]

24 Michael L Fredman and Robert Endre Tarjan

doi: 10.1145/367766.368168. 24 Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the ACM (JACM), 34(3):596–615,

work page doi:10.1145/367766.368168
[17]

Constraint satisfaction problems with advice

25 Suprovat Ghoshal, Konstantin Markarychev, and Yury Markarychev. Constraint satisfaction problems with advice. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 1202–1221. SIAM, 2025.doi:10.1137/1.9781611978322.36. A. Polak and J. Schmidt 19 26 Yufan Huang, Peter Jin, and Kent Quanrud. Faster single-source shor...

work page doi:10.1137/1.9781611978322.36 2025
[18]

27 Donald B

doi:10.1137/1.9781611978322.178. 27 Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks.J. ACM, 24(1):1–13, 1977.doi:10.1145/321992.321993. 28 Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. Sum-of-squares lower bounds for densest k-subgraph. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC...

work page doi:10.1137/1.9781611978322.178 1977
[19]

Almost-polynomial ratio eth-hardness of approximating densest k-subgraph

33 Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 954—-961. ACM, 2017.doi:10.1145/3055399.3055412. 34 Xiao Mao. Fully dynamic all-pairs shortest paths: Likely optimal worst-case update time. In Proceedings of the 56th...

work page doi:10.1145/3055399.3055412 2017
[20]

Discrete-convex-analysis-based framework for warm- starting algorithms with predictions

38 Shinsaku Sakaue and Taihei Oki. Discrete-convex-analysis-based framework for warm- starting algorithms with predictions. InAdvances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022,

2022
[21]

39 Michael Sipser.Introduction to the Theory of Computation

URL: http://papers.nips.cc/paper_files/paper/2022/hash/ 844e61124d9e1f58632bf0c8968ad728-Abstract-Conference.html. 39 Michael Sipser.Introduction to the Theory of Computation. ACM New York, NY, USA,

2022
[22]

On some fine-grained questions in algorithms and complexity

40 Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. InProceedings of the International Congress of Mathematicians (ICM 2018), pages 3447–3487, 2018.doi:10.1142/9789813272880_0188. 41 Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems.J. ACM, 65(5)...

work page doi:10.1142/9789813272880_0188 2018
[23]

Subcubic Equivalences Between Path, Matrix, and Triangle Problems , journal =

doi:10.1145/3186893. 42 Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 3792–3835. SIAM, 2024.doi:10.1137/ 1.9781611977912.134. 43Vijay V Vazirani.Approximation algorithms. Springer,

work page doi:10.1145/3186893 2024
[24]

A theorem on Boolean matrices.J

20 Warm-Starting All-Pairs Shortest Paths with Predictions 44 Stephen Warshall. A theorem on Boolean matrices.J. ACM, 9(1):11–12, 1962.doi:10.1145/ 321105.321107. 45 R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity.SIAM J. Comput., 47(5):1965–1985,

work page arXiv 1962
[25]

46 Raphael Yuster

Announced at STOC 2014.doi:10.1137/15M1024524. 46 Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. InProceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pages 950–957. SIAM, 2009.doi:10.1137/1.9781611973068.103. 47 Rui Zhu, Bang Liu, Di Niu, Zongpeng Li, and Hong Vicky Z...

work page doi:10.1137/15m1024524 2014

[1] [1]

2 Ittai Abraham, Shiri Chechik, and Sebastian Krinninger

URL: https: //proceedings.mlr.press/v267/aamand25c.html. 2 Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 440–452. SIAM,

2017

[2] [2]

3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou

doi:10.1137/1.9781611974782.28. 3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 2005–2039. SIAM,

work page doi:10.1137/1.9781611974782.28 2025

[3] [3]

4Noga Alon and Joel H Spencer.The probabilistic method

doi:10.1137/1.9781611978322.63. 4Noga Alon and Joel H Spencer.The probabilistic method. John Wiley & Sons,

work page doi:10.1137/1.9781611978322.63

[4] [4]

net/forum?id=AEFVa6VMu1

URL: https://openreview. net/forum?id=AEFVa6VMu1. 6 Benny Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions.SIAM Journal on Computing, 42:2008–2037,

2008

[5] [5]

7 Xingjian Bai and Christian Coester

doi:10.1137/ 120884857. 7 Xingjian Bai and Christian Coester. Sorting with predictions. InAdvances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023,

2023

[6] [6]

8 Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen

URL: http://papers.nips.cc/paper_files/paper/ 2023/hash/544696ef4847c903376ed6ec58f3a703-Abstract-Conference.html. 8 Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single- source shortest paths in near-linear time.J. ACM, 72(4):1–34,

2023

[7] [7]

9 Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan

Announced at FOCS 2022.doi:10.1145/3742890. 9 Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an o(n¼) approximation for densest k-subgraph. InProceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pages 201—-210. ACM, 2010.doi:10.1145/1806689.1806719. 10 Ja...

work page doi:10.1145/3742890 2022

[8] [8]

12 Timothy M

doi:10.1145/2840728.2840746. 12 Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Fredman’s trick meets dominance product: Fine-grained complexity of unweighted APSP, 3SUM counting, and more. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 419–432. ACM, 2023.doi:10.1145/3564246.3585237. 13 Justin Y. Ch...

work page doi:10.1145/2840728.2840746 2023

[9] [9]

15 Eden Chlamtáč, Michael Dinitz, and Yury Makarychev

Announced at APPROX/RANDOM 2016.doi:10.1137/16M1096402. 15 Eden Chlamtáč, Michael Dinitz, and Yury Makarychev. Minimizing the union: tight approx- imations for small set bipartite vertex expansion. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 881—-899. SIAM,

work page doi:10.1137/16m1096402 2016

[10] [10]

16 Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang

doi:10.1137/1.9781611974782.56. 16 Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster Ford-Fulkerson. InInternational Conference on Machine Learning, ICML 2023, volume 202 ofProceedings of Machine Learning Research, pages 7231–7248. PMLR,

work page doi:10.1137/1.9781611974782.56 2023

[11] [11]

17 Sami Davies, Sergei Vassilvitskii, and Yuyan Wang

URL: https://proceedings.mlr.press/v202/davies23b.html. 17 Sami Davies, Sergei Vassilvitskii, and Yuyan Wang. Warm-starting push-relabel. InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024,

2024

[12] [12]

18 Edsger W

URL: http://papers.nips.cc/paper_files/ paper/2024/hash/39ec972afab01e0d8ddc6834a9d12ac1-Abstract-Conference.html. 18 Edsger W. Dijkstra. A note on two problems in connexion with graphs.Numerische Mathematik, 1:269–271, 1959.doi:10.1007/BF01386390. 19 Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvit- skii. Faster matchi...

work page doi:10.1007/bf01386390 2024

[13] [13]

20 Jon C

URL:https://proceedings.neurips.cc/paper/2021/hash/ 5616060fb8ae85d93f334e7267307664-Abstract.html. 20 Jon C. Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou. Learning- augmented k-means clustering. InInternational Conference on Learning Representations, ICLR 2022,

2021

[14] [14]

21 Jeremy T

URL:https://openreview.net/forum?id=X8cLTHexYyY. 21 Jeremy T. Fineman. Single-source shortest paths with negative real weights in˜O(mn8/9)time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 3–14. ACM, 2024.doi:10.1145/3618260.3649614. 22 Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, and Aurelio ...

work page doi:10.1145/3618260.3649614 2024

[15] [15]

23 Robert W

doi:10.1137/1.9781611978315.17. 23 Robert W. Floyd. Algorithm 97: Shortest path.Commun. ACM, 5(6):345,

work page doi:10.1137/1.9781611978315.17

[16] [16]

24 Michael L Fredman and Robert Endre Tarjan

doi: 10.1145/367766.368168. 24 Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the ACM (JACM), 34(3):596–615,

work page doi:10.1145/367766.368168

[17] [17]

Constraint satisfaction problems with advice

25 Suprovat Ghoshal, Konstantin Markarychev, and Yury Markarychev. Constraint satisfaction problems with advice. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 1202–1221. SIAM, 2025.doi:10.1137/1.9781611978322.36. A. Polak and J. Schmidt 19 26 Yufan Huang, Peter Jin, and Kent Quanrud. Faster single-source shor...

work page doi:10.1137/1.9781611978322.36 2025

[18] [18]

27 Donald B

doi:10.1137/1.9781611978322.178. 27 Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks.J. ACM, 24(1):1–13, 1977.doi:10.1145/321992.321993. 28 Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. Sum-of-squares lower bounds for densest k-subgraph. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC...

work page doi:10.1137/1.9781611978322.178 1977

[19] [19]

Almost-polynomial ratio eth-hardness of approximating densest k-subgraph

33 Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 954—-961. ACM, 2017.doi:10.1145/3055399.3055412. 34 Xiao Mao. Fully dynamic all-pairs shortest paths: Likely optimal worst-case update time. In Proceedings of the 56th...

work page doi:10.1145/3055399.3055412 2017

[20] [20]

Discrete-convex-analysis-based framework for warm- starting algorithms with predictions

38 Shinsaku Sakaue and Taihei Oki. Discrete-convex-analysis-based framework for warm- starting algorithms with predictions. InAdvances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022,

2022

[21] [21]

39 Michael Sipser.Introduction to the Theory of Computation

URL: http://papers.nips.cc/paper_files/paper/2022/hash/ 844e61124d9e1f58632bf0c8968ad728-Abstract-Conference.html. 39 Michael Sipser.Introduction to the Theory of Computation. ACM New York, NY, USA,

2022

[22] [22]

On some fine-grained questions in algorithms and complexity

40 Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. InProceedings of the International Congress of Mathematicians (ICM 2018), pages 3447–3487, 2018.doi:10.1142/9789813272880_0188. 41 Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems.J. ACM, 65(5)...

work page doi:10.1142/9789813272880_0188 2018

[23] [23]

Subcubic Equivalences Between Path, Matrix, and Triangle Problems , journal =

doi:10.1145/3186893. 42 Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 3792–3835. SIAM, 2024.doi:10.1137/ 1.9781611977912.134. 43Vijay V Vazirani.Approximation algorithms. Springer,

work page doi:10.1145/3186893 2024

[24] [24]

A theorem on Boolean matrices.J

20 Warm-Starting All-Pairs Shortest Paths with Predictions 44 Stephen Warshall. A theorem on Boolean matrices.J. ACM, 9(1):11–12, 1962.doi:10.1145/ 321105.321107. 45 R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity.SIAM J. Comput., 47(5):1965–1985,

work page arXiv 1962

[25] [25]

46 Raphael Yuster

Announced at STOC 2014.doi:10.1137/15M1024524. 46 Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. InProceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pages 950–957. SIAM, 2009.doi:10.1137/1.9781611973068.103. 47 Rui Zhu, Bang Liu, Di Niu, Zongpeng Li, and Hong Vicky Z...

work page doi:10.1137/15m1024524 2014