CS Paper Radar

Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time

Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams

cs.DS ·submitted 2026-10-15 16:09 UTC · v1
top venue

Abstract

In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained complexity, both from the upper- and lower-bound side: * From the upper-bound side, for each of these problems the authors give an intermediate running time strictly between $n^ω$ and $n^3$, where $ω<2.371177$ is the matrix multiplication exponent. When optimized, this running time can be made $\tilde{\mathcal{O}}(n^{(3+ω)/2})$. By now, many more problems can be solved in this running time: directed unweighted or node-weighted APSP, a variety of matrix products such as max-min and dominance, RNA Folding and many more. For some of these, the community has also developed tools suggesting that this intermediate running time is necessary. * From the lower-bound side, the authors give lower bounds of $n^{ω-o(1)}$, conditioned on three natural hardness hypotheses on the complexity of quantified variants of triangle detection that account for different types of hardness of such problems. Despite this, it has remained open for over 20 years which of these two pieces of evidence reflects the truth for the problems that Kratsch and Spinrad study: whether the intermediate running time is indeed necessary and stronger lower bounds hold, or whether the hardness evidence of Kratsch and Spinrad is essentially tight. In this paper, we resolve this question and show that the latter is the case: all problems admit an $\tilde{\mathcal{O}}(n^ω)$ time algorithm. As an additional contribution, we make partial algorithmic progress on further problems in structural graph theory of intermediate complexity, improving over previous work [Chiu and Lu, STACS 2022 and Information and Computation 2024][Spinrad, Discrete Applied Math 2004].

Comment
32 pages, 6 figures; to appear at SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

cs.DS ·2026-11-04 ·Piaoyang Cui, Yiming Liu, David P. Woodruff
similarity 0.70
Abstract

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

0.20

Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

cs.DS cs.CCcs.DMmath.CO ·2026-08-25 ·Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk
similarity 0.69
Abstract · 31 pages, 5 figures

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

0.37

Simple, Faster (min, +) Matrix Multiplication and APSP

cs.DS ·2026-10-14 ·Barna Saha, Christopher Ye
theory similarity 0.67
Abstract · 17 pages

In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.

0.46

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

cs.CC ·2026-10-01 ·Isaac Rudich, Louis-Martin Rousseau
publishedtheory similarity 0.64
Abstract

Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.

0.19

Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$

cs.CC ·2026-10-27 ·Eric Binnendyk
theory similarity 0.64
Abstract

It is known that the problem of recognizing the existence of a unit-distance realization in $\mathbb{Z}^d$ for a graph $G$ is NP-complete. Here, assuming ETH, we give a sub-exponential lower bound of $2^{Ω(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{Ω(n^{2/3})}$ in $\mathbb{Z}^3$, and give an upper bound of $2^{O(n^{(d-1)/d} (\log n)^2)}$ for the time complexity with an explicit divide-and-conquer algorithm. This approach beats naive exhaustive search by a factor of $\tildeΩ(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.

0.27

The Komlós Problem in Matrix-Multiplication Time

cs.DS cs.DM ·2026-10-14 ·Emile Anand, Peter Chen
similarity 0.62
Abstract · 30 pages

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.

0.39

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

cs.DS ·2026-11-01 ·Yang Cao, Haoran Qi, Hanzhi Wang
similarity 0.62
Abstract

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O(mn^{k-1})$-time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has remained the fastest for every $k\geq3$ for over four decades, even when the paths must be shortest. We break this bound for every $k\geq3$ with randomized algorithms running in expected $O_k(m+n^{k-3+ω+\varepsilon})$ time for every $\varepsilon>0$, where $ω<2.372$ is the matrix multiplication exponent; this is $O_k(m+n^{k-0.62})$. For two disjoint shortest paths, we find the paths as fast as we detect them: in expected linear time on DAGs and on undirected graphs with polynomially bounded integer weights, and in expected $O(\min\{mn,n^{ω+\varepsilon}\})$ time on directed graphs whose cycles have positive weight, which on dense graphs is $o(mn)$ even for detection. All algorithms evaluate a polynomial whose monomials are the solutions: a new first-collision circuit speeds up the evaluation in DAGs, and a correlated extraction step at cuts crossed once by every path finds a solution at the cost of a constant number of evaluations.

0.20

Fast Spectral Signing for Vector Balancing

cs.DS ·2026-09-24 ·Xiaoyu Li
theoryhighly cited similarity 0.62
Abstract

The Komlós conjecture, now a theorem, asserts that whenever the columns of a matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every coordinate of $A\varepsilon$ bounded by an absolute constant. Guo, Fang, and Lu gave the first polynomial-time algorithm for finding such signs, a deterministic spectral signing procedure with discrepancy $8272$ and running time $O((mn^9+n^{10})\log(m+n))$. We give a deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations, where $ω>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $ω$ this is $\widetilde O(mn+n^{4.372})$. Our algorithm uses the same framework: it rounds a single fractional coloring and watches all rows through the top eigenvalue of a Gram matrix of energy-corrected barriers. Steps follow flat directions, rescaled so that no barrier near its threshold moves faster than a constant, and the regularizer grows as coordinates freeze; together these bound the number of updates by $O(n^2\log n)$. A weak quadratic charge on the tracked row sums leaves $O(n\log^2 n)$ rows to evaluate at any time, and a motion clock bounds when any other row could approach its barrier. Each update is a short sequence of matrix products. Its direction is read off by conditional expectations from a polynomial soft projector, its small constraint residual is repaired in affine row representations, and one identity accounts for every change of representation. For rational input the algorithm has polynomial bit complexity.

0.32