betaFeedback

WorksComputer Science

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Abstract

We give the first polynomial improvements over the textbook algorithms for 33SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve 33SUM on nn integers of polynomial size in O(n1.9992)O(n^{1.9992}) time and APSP on directed nn-vertex graphs with polynomially bounded integer weights in O(n2.9995)O(n^{2.9995}) time. This refutes the 33SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the 33SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight kk-Clique hypotheses, and the three rectangular hinted Online Matrix–Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let XX be an N×DN\times D integer matrix and YY a D×ND\times N integer matrix with D≤N1/18D\le N^{1/18}, and let WW be any set of at most N2/DN^2/\sqrt D positions. We compute the entries (XY)[I,J](XY)[I,J], (I,J)∈W(I,J)\in W, in O(N2/D0.063)O(N^2/D^{0.063}) operations, which is polynomially less than the time needed to write down XYXY or to compute N2/DN^2/\sqrt D inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in WW, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have nn vertices but one part has nεn^{\varepsilon} vertices for ε<0.12\varepsilon<0.12. By known reductions, Exact Triangle, and hence 33SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of XYXY, not known in advance.

Claude, an AI model developed by Anthropic, discovered the algorithm that refutes the 3SUM, APSP, and Exact Triangle hypotheses. The authors then worked to understand, simplify, strengthen, and extend the algorithm, derive additional consequences, and make the presentation accessible. See “Acknowledgments and Methodology” for how the result was found and shared with the authors. The authors take full responsibility for this paper.

Claude also verified this paper’s main results using the Lean 4 proof assistant with the Mathlib library.

Introduction

Since its inception, algorithms research has sought the fastest possible algorithm for every problem it considers. Powerful techniques have been developed, from variants of dynamic programming to surprising algebraic tools such as the Fast Fourier Transform [65] and fast matrix multiplication [147]. Yet for many problems, these techniques have not sufficed. Some examples include:

  • 3SUM: Given nn numbers, decide whether three of them sum to 0. This is a classical problem with a long history, and it is central to computational geometry (see [92]). Despite many decades of research, the O(n2)O(n^2)-time algorithm taught in algorithms classes has only been sped up by polylogarithmic factors [35, 94, 55].

  • All-Pairs Shortest Paths (APSP): Given an edge-weighted graph on nn vertices with no negative cycles, compute the shortest-path distance between every pair of vertices. Classical algorithms such as Johnson’s [107] and Floyd and Warshall’s [85, 162] solve APSP in O(n3)O(n^3) time. After a long line of work [87, 150, 76, 97, 151, 152, 173, 52, 98, 53, 102], the fastest known algorithm [166] only shaves a subpolynomial, 2Ω(log⁡n)2^{\Omega(\sqrt{\log n})} factor off the cubic running time.

  • Directed Unweighted APSP: The version of APSP in nn-vertex directed unweighted graphs. The fastest known algorithm, by Zwick [172], runs in O(n2.5275)O(n^{2.5275}) time with the current bounds for rectangular matrix multiplication [10], and beyond improvements to the matrix multiplication bounds, it has not been improved for more than two decades. If the exponent ω\omega of matrix multiplication is 2, the best known running time for this problem [14, 172] is still only O~(n2.5)\widetilde{O}(n^{2.5}).

  • Tree Edit Distance: Given two rooted, ordered, labeled trees with nn vertices, and costs for deleting, inserting, and relabeling vertices, find the cheapest sequence of such operations that transforms one tree into the other. Tree Edit Distance is used, for instance, to compare RNA secondary structures and XML documents. The fastest known algorithms for this problem [75, 133] run in cubic time, up to subpolynomial improvements. Only when all costs are equal to 1 are truly subcubic algorithms known [127, 74, 133].

  • Online Set Disjointness: Preprocess sets S1,…,SNS_1,\ldots,S_N and T1,…,TNT_1,\ldots,T_N over a universe of size DD, so that given II and JJ one can quickly decide whether SI∩TJ=∅S_I \cap T_J = \emptyset, or, in the counting version, return ∣SI∩TJ∣\lvert S_I \cap T_J\rvert. Essentially only two straightforward solutions are known: (1) to compute all N2N^2 answers in advance, which fast rectangular matrix multiplication does in N2+o(1)N^{2+o(1)} time when D≤N0.321D \le N^{0.321} [64, 161], and (2) to store the sets and compute each intersection at query time in O(D)O(D) time. Set Disjointness data structures have been studied extensively [50, 116, 89, 155, 119], mostly for sets of small total size over a large universe.

  • CNF-SAT: Given a Boolean formula FF in conjunctive normal form over nn variables and O(n)O(n) clauses, is there an assignment to the variables that satisfies all clauses? The brute-force algorithm solves CNF-SAT in 2npoly⁡(n)2^n\operatorname{poly}(n) time. There are slightly faster algorithms when the width of the clauses is bounded by a constant independent of nn [144, 136, 99]. However, no O(1.99999n)O(1.99999^n)-time algorithm is known.

  • Orthogonal Vectors (OV): Given nn Boolean vectors in d=ω(log⁡n)d = \omega(\log n) dimensions, are two of them orthogonal? The brute-force algorithm solves OV in O(n2d)O(n^2d) time, and only subpolynomial improvements are known: the fastest algorithms [29, 66] run in n2−1/O(log⁡(d/log⁡n))n^{2-1/O(\log(d/\log n))} time.

The apparent lack of progress on problems such as these led to new theories of hardness: NP-completeness [61, 110] for problems with no known polynomial-time algorithm, and fine-grained complexity (FGC) [154, 45] for problems whose best known algorithms were stuck at essentially the straightforward running time. Both theories relate problems via reductions. FGC focuses on improvements in the exponent: a fine-grained reduction from problem AA to problem BB with respect to running times a(n)a(n) and b(n)b(n) implies that an O(b(n)1−ε)O(b(n)^{1-\varepsilon})-time algorithm for BB for some ε>0\varepsilon> 0 can be converted into an O(a(n)1−δ)O(a(n)^{1-\delta})-time algorithm for AA for some δ>0\delta> 0.

Fine-grained complexity took three of the problems from our list above and postulated that the state-of-the-art algorithms cannot be beaten: in the word RAM model of computation with O(log⁡n)O(\log n)-bit words, APSP with polynomially bounded integer weights requires n3−o(1)n^{3-o(1)} time (the “APSP hypothesis” [140, 157, 159, 26]), 3SUM on nn integers of polynomial size requires n2−o(1)n^{2-o(1)} time (the “3SUM hypothesis” [92, 136]), and there is no ε>0\varepsilon> 0 such that CNF-SAT on nn variables and O(n)O(n) clauses can be solved in (2−ε)n(2-\varepsilon)^n time (the “Strong Exponential Time Hypothesis,” SETH [103, 104, 50]).

Through fine-grained reductions, FGC built a web of relations among problems, and within it, classes of problems that are equivalent to each other (see the surveys [154, 45]). For a large variety of problems for which no improved running times had been obtained in decades, FGC pointed to reasons: they are 3SUM-hard, APSP-hard, SETH-hard, or worse. In other words, to improve the known algorithms, one knew which obstacle needed to be overcome.

For instance, many problems are known to be equivalent to APSP under fine-grained reductions. Either all of the following problems are solvable in truly subcubic time, meaning in O(n3−ε)O(n^{3-\varepsilon}) time for some constant ε>0\varepsilon> 0 (truly subquadratic is defined similarly), or none of them is: the (min⁡,+)(\min,+)-product A⋆BA \star B of two n×nn \times n matrices AA and BB (defined by (A⋆B)[i,j]=min⁡k(A[i,k]+B[k,j])(A \star B)[i,j] = \min_k(A[i,k]+B[k,j])) [87, 19]1, Negative Triangle and Second Shortest Simple Path [157, 159], Graph Radius [30, 17], Tree Edit Distance [39, 133], and many other problems [157, 159, 138, 30, 17], more of which are listed below, after Figure 1. Perhaps surprisingly, it is also known [66] that solving APSP in truly subcubic time would give a polynomially faster algorithm for directed unweighted APSP as well, and the corresponding hypotheses are in fact equivalent [82]2 (albeit conditionally2{}^{2}), even though the longstanding running times of the two problems are different: ≈n3\approx n^3 for APSP and ≈n2.5\approx n^{2.5} for directed unweighted APSP (if ω=2\omega= 2).

Diagram of problems affected by the algorithm and their fine-grained reductions

Figure 1. Problems affected by our algorithm, which solves the problem in the orange box (Lopsided All-Edges Sparse Triangle) directly. The problems inside each of the three thick-bordered blue boxes (3SUM class, Exact Triangle, and APSP class) are pairwise equivalent under fine-grained reductions (for MonoConvolution, whose baseline is n1.5n^{1.5}, this means O(n1.5−ε)O(n^{1.5-\varepsilon}) time), and we omit the arrows between them. Problems in gray boxes are reached from 3SUM, APSP, or Exact Triangle only by one-way reductions, so our result gives no faster algorithms for them, but these reductions no longer give evidence of hardness. The new algorithms are deterministic except where marked. Citations are to the reductions; for the problems in the top rows, the cited papers contain many more problems of the same kind.

Similar reductions and equivalences are also known for 3SUM: all nontrivial 3-linear degeneracy tests are equivalent to 3SUM [73], and many other problems are 3SUM-hard (e.g., many problems in computational geometry [92, 36, 146, 18], and some string problems [6, 26, 116]).

CNF-SAT reduces to Orthogonal Vectors [163], so that unless SETH is refuted, OV requires n2−o(1)n^{2-o(1)} time. SETH also implies fine-grained hardness for many exponential-time problems [50].

Both 3SUM and APSP reduce to the Exact Triangle problem (given a tripartite graph with integer edge weights, is there a triangle whose three weights sum to zero?) [158, 157, 159]. Through Exact Triangle, both reduce to online Set Disjointness (from the list above), and even to its offline version, in which the query pairs are given in advance together with the sets [160, 71]; for 3SUM, direct reductions are also known [136, 116, 109, 1]. In graph terms, offline Set Disjointness is the All-Edges Sparse Triangle problem: given a graph with mm edges, decide for every edge whether it lies in a triangle.

All-Edges Sparse Triangle thus inherits the hardness of both 3SUM and APSP, and it is in turn the source of the conditional lower bounds for Set Disjointness data structures, dynamic graph problems, and other problems [136, 26, 116, 90]. Many came to regard it as one of the most reliably hard problems in fine-grained complexity, and the evidence seemed good.

All-Edges Sparse Triangle can be solved in O(m3/2)O(m^{3/2}) time just by listing all triangles [105, 60], and a high-degree/low-degree split combined with matrix multiplication [14] improves this to O(m2ω/(ω+1))O(m^{2\omega/(\omega+1)}), where 2≤ω<2.3722 \le\omega< 2.372 is the matrix multiplication exponent.3 Even if ω=2\omega= 2, this is m4/3m^{4/3}. On the graphs the reductions produce, which have nn vertices of degree about n\sqrt{n}, this equals the brute-force running time n2n^2 conjectured to be optimal. Matrix multiplication only seemed useful for dealing with dense inputs, whereas these instances ask for a sparse set of outputs, and it seemed plausible that no technique could do better.

However, a reduction from AA to BB, proved in order to show that BB is hard, is also an algorithm for AA whenever BB turns out to be easy. In this paper we give a new algorithm for a lopsided version of All-Edges Sparse Triangle, in which the graph is tripartite and one of the three parts is significantly smaller than the other two. Most known reductions to All-Edges Sparse Triangle can be slightly modified to produce such instances.

As a consequence, all of the problems in the list above (and many more), except for CNF-SAT and Orthogonal Vectors, have polynomially faster algorithms than before:

  • 3SUM: deterministic O(n1.9992)O(n^{1.9992}) time for integers of polynomial size (Theorem 22), and for real numbers, a Las Vegas algorithm with O(n1.998)O(n^{1.998}) expected time whose only operations on real numbers are comparisons, additions, and subtractions (Theorem 35).

  • APSP: deterministic O(n2.9995)O(n^{2.9995}) time for polynomially bounded integer weights, and the same bound for the (min⁡,+)(\min,+)-product (Theorem 22), and for real weights, Las Vegas algorithms with O(n2.998)O(n^{2.998}) expected time, again using only comparisons, additions, and subtractions on real numbers (Theorem 35).

  • Directed Unweighted APSP: a deterministic algorithm running in O(n2+μ−ε′′)O(n^{2+\mu-\varepsilon''}) time for some constant ε′′>0\varepsilon'' > 0, where μ<0.5275\mu< 0.5275 is defined by ω(1,μ,1)=1+2μ\omega(1,\mu,1) = 1 + 2\mu, and ω(1,μ,1)\omega(1,\mu,1) is the exponent of multiplying an n×nμn \times n^\mu by an nμ×nn^\mu\times n matrix. Note that O(n2+μ)≤O(n2.5275)O(n^{2+\mu}) \le O(n^{2.5275}) is the longstanding running time of Zwick’s algorithm. This is the first improvement over Zwick’s algorithm that does not come from faster rectangular matrix multiplication, and it refutes the Directed Unweighted APSP hypothesis [66, 68, 84] (Theorem 34).

  • Tree Edit Distance: O(n2.9995)O(n^{2.9995}) time for polynomially bounded integer costs via the tight reduction of [39].

  • Online Set Disjointness: for D≤N0.12D \le N^{0.12}, a deterministic data structure whose preprocessing time is polynomially less than N2N^2 and whose query time is polynomially less

than D\sqrt{D}, and which returns ∣SI∩TJ∣|S_I \cap T_J|, so that it solves the counting version as well. For D≤N1/18D \le N^{1/18}, the preprocessing takes O(N2/D0.063)O(N^2/D^{0.063}) time and the queries take O(D0.437)O(D^{0.437}) time (Theorem 3).

The APSP and 3SUM hypotheses are therefore refuted, and so are several other hypotheses of fine-grained complexity. Figure 1 summarizes the problems affected, and in Section 1.2 below we list many more new algorithmic results. All of these results follow from one algorithm, for computing a given sparse set of entries of the product of two thin matrices, which we describe in the next subsection.

We view this as a great success for fine-grained complexity. The hypotheses were made to be tested. The reductions and connections between problems have always been the focus of fine-grained complexity, and these connections persist whether or not the problems turn out to be hard. The web of reductions that was interpreted to imply hardness is exactly what turns a single new algorithm into faster algorithms for a myriad of problems at once. This also opens a number of research directions in fine-grained complexity, algorithm design, and algebraic complexity; we discuss some in Section 6.

All-Edges Sparse Triangle

In this paper we present a simple algebraic technique that solves All-Edges Sparse Triangle in O(n2−δ)O(n^{2-\delta}) time, for a constant δ>0\delta> 0, on sparse tripartite graphs with two parts of nn vertices and a third part of at most n0.12n^{0.12} vertices. In matrix language it computes a prescribed sparse set of entries of a dense product of thin matrices. We call a product of an N×DN \times D matrix by a D×ND \times N matrix thin when DD is a small power of NN, and, given a set WW of positions of the product, we call these positions, and the entries of the product at them, wanted. Unlike in usual fast matrix multiplication algorithms, the wanted entries are a sparse subset of the full matrix product, and our new algorithm critically exploits this. A matrix multiplication algorithm computes all N2N^2 entries of the product whether they are wanted or not, and thus takes Ω(N2)\Omega(N^2) time, whereas ours is faster than this. Our theorem is as follows.

Theorem 1 (see Corollary 26 and Theorem 25). Let N≥D18N \ge D^{18}, let X∈ZN×DX \in\mathbb{Z}^{N \times D} and Y∈ZD×NY \in\mathbb{Z}^{D \times N} have entries of absolute value NO(1)N^{O(1)}, and let WW be any set of ∣W∣≤N2/D|W| \le N^2/\sqrt{D} positions. The entries (XY)[I,J](XY)[I,J], (I,J)∈W(I,J) \in W, can be computed deterministically in O(N2/D0.063)O(N^2/D^{0.063}) operations on O(log⁡N)O(\log N)-bit integers. More generally, for every ε<0.1204\varepsilon< 0.1204 and every κ>0\kappa> 0 there is a γ>0\gamma> 0 such that, whenever D≤NεD \le N^\varepsilon and ∣W∣≤N2/Dκ|W| \le N^2/D^\kappa, the task takes O(N2/Dγ)O(N^2/D^\gamma) operations.

References

  1. [1][ABF23] Amir Abboud, Karl Bringmann, and Nick Fischer. Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics. In Proc. 55th ACM Symposium on Theory of Computing (STOC 2023), pages 391–404, 2023.
  2. [2][ABFK24] Amir Abboud, Karl Bringmann, Nick Fischer, and Marvin Künnemann. The time complexity of fully sparse matrix multiplication. In Proc. 35th ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 4670–4703, 2024.arxiv.org/abs/2309.06317
  3. [3]Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. Hardness of approximation in P via short cycle removal: Cycle detection, distance oracles, and beyond. In Proc. 54th ACM Symposium on Theory of Computing (STOC 2022), pages 1487–1500, 2022. Full version: arXiv:2204.10465.arxiv.org/abs/2204.10465
  4. [4]Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. Journal of the ACM, 52(2):157–171, 2005.
  5. [6]Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), volume 8572 of LNCS, pages 114–125, 2014.arxiv.org/abs/1405.0189
  6. [7]Josh Alman, Timothy M. Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016), pages 467–476, 2016.arxiv.org/abs/1608.04355
  7. [8]Josh Alman, Timothy M. Chan, and R. Ryan Williams. Faster deterministic and Las Vegas algorithms for offline approximate nearest neighbors in high dimensions. In Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 637–649, 2020.
  8. [9]Vladimir L. Arlazarov, Efim A. Dinic, Mikhail A. Kronrod, and Igor A. Faradžev. On economical construction of the transitive closure of an oriented graph. Soviet Mathematics Doklady, 11:1209–1210, 1970.
  9. [10]Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proc. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 2005–2039, 2025.arxiv.org/abs/2404.16349
  10. [11]Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka. New graph decompositions and combinatorial Boolean matrix multiplication algorithms. In Proc. 56th ACM Symposium on Theory of Computing (STOC 2024), pages 935–943, 2024.arxiv.org/abs/2311.09095
  11. [12]Amir Abboud, Shon Feller, and Oren Weimann. On the fine-grained complexity of parity problems. In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of LIPIcs, pages 5:1–5:19, 2020.arxiv.org/abs/2002.07415
  12. [13]Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.DOI
  13. [14]Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255–262, 1997.DOI
  14. [15]Noga Alon, Zvi Galil, Oded Margalit, and Moni Naor. Witnesses for Boolean matrix multiplication and for shortest paths. In Proc. 33rd IEEE Symposium on Foundations of Computer Science (FOCS 1992), pages 417–426, 1992.DOI
  15. [16]Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1681–1697, 2015.
  16. [17]Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP, and diameter. ACM Transactions on Algorithms, 19(1):3:1–3:30, 2023.
  17. [18]Boris Aronov and Sariel Har-Peled. On approximating the depth and related problems. SIAM Journal on Computing, 38(3):899–921, 2008.
  18. [19]Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
  19. [20]Josh Alman, Yizhi Huang, and Kevin Yeo. Fine-grained complexity in a world without cryptography. In Advances in Cryptology – EUROCRYPT 2025, Part VII, volume 15607 of LNCS, pages 375–405, 2025.DOI
  20. [21]Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013), volume 7965 of LNCS, pages 1–12, 2013.arxiv.org/abs/1304.7558
  21. [22]Josh Alman and Baitian Li. Kronecker powers, orthogonal vectors, and the asymptotic spectrum. In Proc. 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025), pages 1411–1441, 2025. arXiv:2509.14489.arxiv.org/abs/2509.14489
  22. [23]Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In Proc. 22nd European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 1–12, 2014.arxiv.org/abs/1311.3054
  23. [24]Noga Alon and Moni Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16(4–5):434–449, 1996.
  24. [25]Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In Proc. 12th International Conference on Database Theory (ICDT 2009), pages 121–126, 2009.
  25. [26]Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS 2014), pages 434–443, 2014.arxiv.org/abs/1402.0054
  26. [28]Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proc. 47th ACM Symposium on Theory of Computing (STOC 2015), pages 41–50, 2015.
  27. [29]Josh Alman and Ryan Williams. Probabilistic polynomials and Hamming nearest neighbors. In Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS 2015), pages 136–150, 2015.DOI
  28. [30]Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 218–230, 2015.
  29. [31]Josh Alman and Hantao Yu. Improving the leading constant of matrix multiplication. In Proc. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 1933–1971, 2025.arxiv.org/abs/2410.20538
  30. [32]Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997.
  31. [33]Austin R. Benson and Grey Ballard. A framework for practical parallel fast matrix multiplication. In Proc. 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015), pages 42–53, 2015.
  32. [34]David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pătrașcu, and Perouz Tasslakian. Necklaces, convolutions, and X + Y. Algorithmica, 69(2):294–314, 2014.
  33. [35]Ilya Baran, Erik D. Demaine, and Mihai Pătrașcu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584–596, 2008.
  34. [36]Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of LIPIcs, pages 81:1–81:13, 2016.arxiv.org/abs/1602.05837
  35. [38]Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, and Evelyn Warton. Output-sparse matrix multiplication using compressed sensing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026), volume 392 of LIPIcs, pages 40:1–40:20, 2026. Full version: arXiv:2508.10250.arxiv.org/abs/2508.10250
  36. [39]Karl Bringmann, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). ACM Transactions on Algorithms, 16(4):48:1–48:22, 2020.
  37. [40]Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Trimmed Moebius inversion and graphs of bounded degree. Theory of Computing Systems, 47(3):637–654, 2010.
  38. [42]Dario Bini. Relations between exact and approximate bilinear algorithms. Applications. Calcolo, 17:87–97, 1980.DOI
  39. [44]Karl Bringmann and Vasileios Nakos. A fine-grained perspective on approximating subset sum and partition. In Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 1797–1815, 2021.arxiv.org/abs/1912.12529
  40. [45]Karl Bringmann. Fine-grained complexity theory (tutorial). In Proc. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of LIPIcs, pages 4:1–4:7, 2019.DOI
  41. [46]Karl Bringmann. Knapsack with small items in near-quadratic time. In Proc. 56th ACM Symposium on Theory of Computing (STOC 2024), pages 259–270, 2024.arxiv.org/abs/2308.03075
  42. [50]Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proc. 7th ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), pages 261–270, 2016.
  43. [51]Timothy M. Chan and Qizheng He. Reducing 3SUM to convolution-3SUM. In Proc. 3rd SIAM Symposium on Simplicity in Algorithms (SOSA 2020), pages 1–7, 2020.DOI
  44. [52]Timothy M. Chan. All-pairs shortest paths with real weights in O(n³/log n) time. Algorithmica, 50(2):236–243, 2008. Preliminary version in WADS 2005.
  45. [53]Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM Journal on Computing, 39(5):2075–2089, 2010.
  46. [54]Timothy M. Chan. Speeding up the four Russians algorithm by about one more logarithmic factor. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 212–217, 2015.DOI
  47. [55]Timothy M. Chan. More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. ACM Transactions on Algorithms, 16(1):7:1–7:23, 2020.
  48. [56]Vašek Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233–235, 1979.DOI
  49. [59]Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. On problems equivalent to (min,+)-convolution. ACM Transactions on Algorithms, 15(1):14:1–14:25, 2019.
  50. [60]Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210–223, 1985.DOI
  51. [61]Stephen A. Cook. The complexity of theorem-proving procedures. In Proc. 3rd ACM Symposium on Theory of Computing (STOC 1971), pages 151–158, 1971.DOI
  52. [62]Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing, 11(3):467–471, 1982.DOI
  53. [63]Don Coppersmith. Rectangular matrix multiplication revisited. Journal of Complexity, 13(1):42–49, 1997.DOI
  54. [64]Hagai Cohen and Ely Porat. Fast set intersection and two-patterns matching. Theoretical Computer Science, 411(40–42):3795–3800, 2010.
  55. [65]James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965.
  56. [66]Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths. In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of LIPIcs, pages 47:1–47:21, 2021. Full version: arXiv:2102.06181, whose numbering we follow.arxiv.org/abs/2102.06181
  57. [67]Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for triangle problems under even more believable hypotheses: Reductions from real APSP, real 3SUM, and OV. In Proc. 54th ACM Symposium on Theory of Computing (STOC 2022), pages 1501–1514, 2022. Full version: arXiv:2203.08356, whose numbering we follow.arxiv.org/abs/2203.08356
  58. [68]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. In Proc. 55th ACM Symposium on Theory of Computing (STOC 2023), pages 419–432, 2023.arxiv.org/abs/2303.14572
  59. [69]Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, 1990.
  60. [71]Timothy M. Chan and Yinzhan Xu. Simpler reductions from exact triangle. In Proc. 7th SIAM Symposium on Simplicity in Algorithms (SOSA 2024), pages 28–38, 2024.arxiv.org/abs/2310.11575
  61. [72]Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, and Matej Balog. Improving the matrix multiplication exponent with modern optimization and AlphaEvolve. arXiv:2608.16884, 2026.arxiv.org/abs/2608.16884
  62. [73]Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya. All non-trivial variants of 3-LDT are equivalent. In Proc. 52nd ACM Symposium on Theory of Computing (STOC 2020), pages 974–981, 2020.DOI
  63. [74]Lech Duraj, Krzysztof Kleiner, Adam Polak, and Virginia Vassilevska Williams. Equivalences between triangle and range query problems. In Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 30–47, 2020.DOI
  64. [75]Erik D. Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms, 6(1):2:1–2:19, 2009.
  65. [76]Włodzimierz Dobosiewicz. A more efficient algorithm for the min-plus multiplication. International Journal of Computer Mathematics, 32(1–2):49–60, 1990.DOI
  66. [77]Martin Dietzfelbinger, Philipp Schlag, and Stefan Walzer. A subquadratic algorithm for 3XOR. In Proc. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 59:1–59:15, 2018.arxiv.org/abs/1804.11086
  67. [79]Jeff Erickson. Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science, 1999(8), 1999.
  68. [82]Nick Fischer. Universe reduction for APSP: Equivalence of three fine-grained hypotheses. In Proc. 58th ACM Symposium on Theory of Computing (STOC 2026), pages 922–932, 2026.
  69. [83]Nick Fischer, Ce Jin, and Yinzhan Xu. New applications of 3SUM-counting in fine-grained complexity and pattern matching. In Proc. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 4547–4595, 2025.arxiv.org/abs/2410.20764
  70. [84]Nick Fischer, Piotr Kaliciak, and Adam Polak. Deterministic 3SUM-hardness. In Proc. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of LIPIcs, pages 49:1–49:24, 2024. Full version: arXiv:2310.12913, whose numbering we follow.arxiv.org/abs/2310.12913
  71. [85]Robert W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962.DOI
  72. [87]Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM Journal on Computing, 5(1):83–89, 1976.DOI
  73. [88]Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan. Data structures meet cryptography: 3SUM with preprocessing. In Proc. 52nd ACM Symposium on Theory of Computing (STOC 2020), pages 294–307, 2020.DOI
  74. [89]Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Proc. 15th Algorithms and Data Structures Symposium (WADS 2017), volume 10389 of LNCS, pages 421–436, 2017.DOI
  75. [90]Isaac Goldstein, Moshe Lewenstein, and Ely Porat. On the hardness of set disjointness and set intersection with bounded universe. In Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), volume 149 of LIPIcs, pages 7:1–7:22, 2019.arxiv.org/abs/1910.00831
  76. [91]Zvi Galil and Oded Margalit. Witnesses for Boolean matrix multiplication and for transitive closure. Journal of Complexity, 9(2):201–221, 1993.DOI
  77. [92]Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry: Theory and Applications, 5(3):165–185, 1995.
  78. [93]Irving J. Good. The interaction algorithm and practical Fourier analysis. Journal of the Royal Statistical Society, Series B, 20(2):361–372, 1958.
  79. [94]Allan Grøn­lund and Seth Pettie. Threesomes, degenerates, and love triangles. Journal of the ACM, 65(4):22:1–22:25, 2018.
  80. [95]Omar Graia. Optimal deterministic fully sparse matrix multiplication. arXiv:2608.18496, 2026.arxiv.org/abs/2608.18496
  81. [97]Yijie Han. Improved algorithm for all pairs shortest paths. Information Processing Letters, 91(5):245–250, 2004.DOI
  82. [98]Yijie Han. An O(n³(log log n/ log n)⁵⧸⁴) time algorithm for all pairs shortest path. Algorithmica, 51(4):428–434, 2008. Preliminary version in ESA 2006.DOI
  83. [99]Timon Hertli. 3-SAT faster and simpler—unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing, 43(2):718–729, 2014.
  84. [100]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. 47th ACM Symposium on Theory of Computing (STOC 2015), pages 21–30, 2015.DOI
  85. [101]Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak. Dynamic deterministic constant-approximate distance oracles with nᵋ worst-case update time. In Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024), pages 2033–2044, 2024.
  86. [102]Yijie Han and Tadao Takaoka. An O(n³ log log n/ log² n) time algorithm for all pairs shortest paths. Journal of Discrete Algorithms, 38–41:9–19, 2016. Preliminary version in SWAT 2012.
  87. [103]Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367–375, 2001.DOI
  88. [104]Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001.
  89. [105]Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413–423, 1978.
  90. [106]Ce Jin. 0-1 knapsack in nearly quadratic time. In Proc. 56th ACM Symposium on Theory of Computing (STOC 2024), pages 271–282, 2024.arxiv.org/abs/2308.04093
  91. [107]Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1–13, 1977.DOI
  92. [108]Zahra Jafargoli and Emanuele Viola. 3SUM, 3XOR, triangles. Algorithmica, 74(1):326–343, 2016.
  93. [109]Ce Jin and Yinzhan Xu. Removing additive structure in 3SUM-based reductions. In Proc. 55th ACM Symposium on Theory of Computing (STOC 2023), pages 405–418, 2023.
  94. [110]Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.
  95. [111]Leslie Robert Kerr. The Effect of Algebraic Structure on the Computational Complexity of Matrix Multiplication. PhD thesis, Cornell University, 1970.
  96. [112]David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22(6):1199–1217, 1993.
  97. [113]Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. Journal of the ACM, 66(3):16:1–16:18, 2019.
  98. [114]Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. In Proc. 48th International Symposium on Symbolic and Algebraic Computation (ISSAC 2023), pages 381–388, 2023.arxiv.org/abs/2212.01175
  99. [115]Tsvi Kopelowitz and Ely Porat. The strong 3SUM-INDEXING conjecture is false. arXiv:1907.11206, 2019.arxiv.org/abs/1907.11206
  100. [116]Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Proc. 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 1272–1287, 2016.
  101. [118]Elaye Karstadt and Oded Schwartz. Matrix multiplication, a little faster. Journal of the ACM, 67(1):1:1–1:31, 2020. Preliminary version in SPAA 2017.
  102. [119]Tsvi Kopelowitz and Virginia Vassilevska Williams. Towards optimal set-disjointness and set-intersection data structures. In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of LIPIcs, pages 74:1–74:16, 2020.
  103. [120]François Le Gall. Faster algorithms for rectangular matrix multiplication. In Proc. 53rd IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 514–523, 2012.DOI
  104. [121]Rio LaVigne, Andrea Lincoln, and Virginia Vassilevska Williams. Public-key cryptography in the fine-grained setting. In Advances in Cryptology – CRYPTO 2019, Part III, volume 11694 of LNCS, pages 605–635, 2019.DOI
  105. [122]László Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4):383–390, 1975.DOI
  106. [123]Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In Proc. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of LIPIcs, pages 53:1–53:18, 2020. Full version: arXiv:2009.14479, whose statement of Theorem 8 we follow.DOI
  107. [124]François Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith–Winograd tensor. In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 1029–1046, 2018.DOI
  108. [125]Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 1236–1252, 2018.arxiv.org/abs/1712.08147
  109. [126]Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic time-space trade-offs for k-SUM. In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of LIPIcs, pages 58:1–58:14, 2016.DOI
  110. [127]Xiao Mao. Breaking the cubic barrier for (unweighted) tree edit distance. In Proc. 62nd IEEE Symposium on Foundations of Computer Science (FOCS 2021), pages 792–803, 2021. Journal version: SIAM J. Comput., pp. FOCS21-195–FOCS21-223, 2023.arxiv.org/abs/2106.02026
  111. [128]John D. Markel. FFT pruning. IEEE Transactions on Audio and Electroacoustics, 19(4):305–311, 1971.DOI
  112. [129]Jiří Matoušek. Computing dominances in Eⁿ. Information Processing Letters, 38(5):277–278, 1991.DOI
  113. [130]Friedhelm Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM, 31(3):668–676, 1984.
  114. [131]Erik Mårtensson and Paul Stankovski Wagner. The number of the beast: Reducing additions in fast matrix multiplication algorithms for dimensions up to 666. In Proc. SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2025), pages 47–60, 2025.DOI
  115. [132]Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.
  116. [133]Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, and Christopher Ye. Faster weighted and unweighted tree edit distance and APSP equivalence. In Proc. 57th ACM Symposium on Theory of Computing (STOC 2025), pages 2167–2178, 2025.arxiv.org/abs/2411.06502
  117. [134]Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv:2506.13131, 2025.arxiv.org/abs/2506.13131
  118. [135]Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 603–610, 2010.DOI
  119. [136]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. Journal of the ACM, 52(3):337–364, 2005.
  120. [137]Rasmus Pagh and Morten Stöckel. The input/output complexity of sparse matrix multiplication. In Proc. 22nd European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 750–761, 2014.arxiv.org/abs/1403.3551
  121. [138]Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS 2011), pages 180–189, 2011.
  122. [139]Liam Roditty and Virginia Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 833–845, 2012.
  123. [140]Liam Roditty and Uri Zwick. On dynamic shortest paths problems. In Proc. 12th European Symposium on Algorithms (ESA 2004), volume 3221 of LNCS, pages 580–591, 2004. Journal version: Algorithmica 61(2):389–401, 2011.
  124. [141]Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse. In Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pages 509–517, 2004.DOI
  125. [142]Henrik V. Sorensen and C. Sidney Burrus. Efficient computation of the DFT with only a subset of input or output points. IEEE Transactions on Signal Processing, 41(3):1184–1200, 1993.DOI
  126. [143]Arnold Schönhage. Partial and total matrix multiplication. SIAM Journal on Computing, 10(3):434–455, 1981.DOI
  127. [144]Uwe Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS 1999), pages 410–414, 1999.
  128. [145]Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences, 51(3):400–403, 1995.
  129. [146]Michael Soss, Jeff Erickson, and Mark H. Overmars. Preprocessing chains for fast dihedral rotations is hard or even impossible. Computational Geometry: Theory and Applications, 26(3):235–246, 2003.
  130. [147]Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354–356, 1969.DOI
  131. [148]Volker Strassen. Vermeidung von Divisionen. Journal für die reine und angewandte Mathematik, 264:184–202, 1973.DOI
  132. [149]Nathan Sheffield, Virginia Vassilevska Williams, and Zoe Xi. The limits of black-box reductions for all-pairs triangle detection. In Proc. 38th ACM-SIAM Symposium on Discrete Algorithms (SODA 2027), 2027. To appear. Full version: arXiv:2608.19092.
  133. [150]Tadao Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters, 43(4):195–199, 1992.
  134. [151]Tadao Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In Proc. 10th International Computing and Combinatorics Conference (COCOON 2004), volume 3106 of LNCS, pages 278–289, 2004.DOI
  135. [152]Tadao Takaoka. An O(n^3 log log n / log n) time algorithm for the all-pairs shortest path problem. Information Processing Letters, 96(5):155–161, 2005.DOI
  136. [154]Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447–3487. World Scientific, 2018.DOI
  137. [155]Jan van den Brand, Danupop Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In Proc. 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 456–480, 2019. Full version: arXiv:1905.05067.arxiv.org/abs/1905.05067
  138. [156]Jan van den Brand, Zhao Song, and Tianyi Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. In Proc. 41st International Conference on Machine Learning (ICML 2024), volume 235 of PMLR, pages 49008–49028, 2024.arxiv.org/abs/2304.02207
  139. [157]Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS 2010), pages 645–654, 2010.
  140. [158]Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal on Computing, 42(3):831–854, 2013.
  141. [159]Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM, 65(5):27:1–27:38, 2018.
  142. [160]Virginia Vassilevska Williams and Yinzhan Xu. Monochromatic triangles, triangle listing and APSP. In Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pages 786–797, 2020. Full version: arXiv:2007.09318, whose numbering we follow.arxiv.org/abs/2007.09318
  143. [161]Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: From alpha to omega. In Proc. 35th ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 3792–3835, 2024.arxiv.org/abs/2307.07970
  144. [162]Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM, 9(1):11–12, 1962.DOI
  145. [163]Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2–3):357–365, 2005.DOI
  146. [164]R. Ryan Williams. The polynomial method in circuit complexity applied to algorithm design (invited talk). In Proc. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of LIPIcs, pages 47–60, 2014.DOI
  147. [165]R. Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short, non-interactive proofs of batch evaluation. In Proc. 31st Computational Complexity Conference (CCC 2016), volume 50 of LIPIcs, pages 2:1–2:17, 2016.arxiv.org/abs/1601.04743
  148. [166]R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM Journal on Computing, 47(5):1965–1985, 2018.
  149. [167]R. Ryan Williams. The orthogonal vectors conjecture and non-uniform circuit lower bounds. In Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024), pages 1372–1387, 2024. ECCC TR24-142.DOI
  150. [168]Frank Yates. The design and analysis of factorial experiments. Technical Communication 35, Imperial Bureau of Soil Science, Harpenden, 1937.
  151. [169]Huacheng Yu. An improved combinatorial algorithm for Boolean matrix multiplication. Information and Computation, 261:240–247, 2018.
  152. [170]Raphael Yuster and Uri Zwick. Answering distance queries in directed graphs using fast matrix multiplication. In Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pages 389–396, 2005.DOI
  153. [171]Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Transactions on Algorithms, 1(1):2–13, 2005.
  154. [172]Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM, 49(3):289–317, 2002.
  155. [173]Uri Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. Algorithmica, 46(2):181–192, 2006. Preliminary version in ISAAC 2004.

Paper details

vlnc:W_s7c8pz9c
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 48

downloads · 7

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents