CS Paper Radar

Optimal Deterministic Fully Sparse Matrix Multiplication

Omar Graia

cs.DS ·submitted 2026-08-19 03:40 UTC · v1

Abstract

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\operatorname{nnz}(A),\operatorname{nnz}(B)=O(n^{δ_{\mathrm{in}}})$ and $\operatorname{nnz}(AB)=O(n^{δ_{\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\!\left(n^{β_R(δ_{\mathrm{in}},\min\{δ_{\mathrm{out}},2δ_{\mathrm{in}}\})+\varepsilon}\right)$$ operations, where $β_R(δ_{\mathrm{in}},δ)$ denotes the maximum of $δ_{\mathrm{in}}$ and $ω_{δ_{\mathrm{in}},R}(a,1,b)$ over all $a,b\in[0,1]$ satisfying $a+b=δ$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{ω_R((δ_{\mathrm{out}}-1)_+,1,1)+\varepsilon})$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\varepsilon})$, for every $δ_\mathrm{out}\le1.321334$, improving the previous deterministic range of $δ_{\mathrm{out}}\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model

cs.DC cs.DS ·2026-11-11 ·Chetan Gupta, Jukka Suomela, Hossein Vahidi
theory similarity 0.75
Abstract · Lean formalization available at https://doi.org/10.5281/zenodo.24127514

We study sparse matrix multiplication in the low-bandwidth model: $n$ computers multiply two $n\times n$ matrices, and each computer can send and receive one $O(\log n)$-bit message per round. The input matrices are uniformly sparse, meaning that there are at most $d$ nonzero entries in each row and column, and the task is to compute a uniformly sparse part of their product. In prior work, Gupta et al.~(SPAA 2022) presented an $O(d^{1.907})$-round algorithm over fields for this problem when the sparsity structure is globally known in advance (this is referred to as the supported setting). The upper bound was later improved to $O(d^{1.832})$ rounds. In this work, we give a deterministic algorithm that solves this problem in $O(d^{3/2})$ rounds in the supported setting, improving the previous bounds over fields and semirings.

0.13

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

cs.DS ·2026-10-14 ·Barna Saha, Christopher Ye
theory similarity 0.70
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

Solving Linear Programs in the Matrix Multiplication Time

cs.DS ·2026-11-05 ·Zhao Song
similarity 0.66
Abstract · 124 pages, 5 figures

We give a randomized algorithm for feasible bounded-box linear programs with $n$ variables and $d\le n=O(d)$ linearly independent equality constraints. For additive accuracy $ε$, its expected running time is $O((n^ω+n^2\log n)\log(1/ε))$, where $ω$ is the matrix multiplication exponent. This answers the matrix-multiplication-time open question posted in Song's Ph.D. thesis [Son19] in this setting.

0.34

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

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

cs.DS cs.CCmath.NA ·2026-09-29 ·Jonathan A. Kelner
similarity 0.63
Abstract

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.

0.09

Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion

cs.IT cs.CC ·2026-11-02 ·Xiaohong Cai, Mingyang Zhu
theoryhot direction similarity 0.63
Abstract · 38 pages, including appendices

We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant. The binary inner-product case resolves the open question of Braverman, Garg, Pankratov, and Weinstein on the optimal dependence of information complexity on the error probability. For inputs in $\mathbb F_2^m$ and error at most $\varepsilon\in[0,1/2]$, the information complexity with output at Bob lies between $(1-2\varepsilon)m-c_0$ and $(1-2\varepsilon)m$, where $c_0<4.772$ is a universal constant. For independent uniform matrices $X\in\mathbb F_q^{t\times m}$ and $Y\in\mathbb F_q^{s\times m}$, where $t\le s$, computing $XY^{\mathsf T}$ with output at Bob and error at most $\varepsilon\in[0,1]$ has information complexity $(1-q^{ts}\varepsilon/(q^{ts}-1))^+mt\log_2q$, up to an additive gap of less than $9.544$ bits. This gap is independent of the matrix dimensions, field size, and error. At zero error, the information complexity is exactly $mt\log_2q$. The information lower bounds for both inner product and matrix multiplication follow from a new Shannon-to-min-entropy theorem for convolution on discrete groups. Let $Q_1,\ldots,Q_k$ be the finitely supported distributions of independent random variables taking values in a discrete group, and let $s$ be the largest support size. We show that if $k\ge\lceil\lfloor\log_2s\rfloor\ln2\rceil$, then the min-entropy of their ordered product is at least the average Shannon entropy of the $Q_i$ minus $c_0$ bits. This holds for arbitrary discrete groups, including infinite and noncommutative groups, even when the input distributions differ. The leading coefficient of the logarithmic threshold is optimal.

0.38

Thin matrix products up to D <= N^0.172 and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems

cs.DS ·2026-10-12 ·Ruhollah Majdoddin
theorycode/datahighly cited similarity 0.62
Abstract · 130 pages. Lean formalisation and scripts: https://github.com/Majdoddin/formal-math

Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with exponents 1.9992 for 3SUM, 2.9983 for Exact Triangle and 2.99942 for APSP. Their algorithm has two steps: a matrix theorem, computing N^2/sqrt(D) prescribed entries of the product of an N x D and a D x N integer matrix in time N^2/D^gamma, gamma > 0, when D <= N^eps, for every eps < 0.1204; and reductions from the three problems to the lopsided sparse triangle problem. We improve both. With Schönhage's five-term partial-product tensor, the matrix theorem holds for every eps < 0.172. The preprint's reductions keep a quarter of the matrix theorem's saving for 3SUM and a half for Exact Triangle and APSP; ours keep all of it, by calling the counting version of the triangle problem adaptively and building composite moduli one prime at a time. Together this gives deterministic 3SUM in n^{1.9945+o(1)}, and Exact Triangle, (min,+)-product and APSP in n^{2.9945+o(1)}. We also improve on the preprint's proof sketch for 3XOR and solve it deterministically in O(n^{1.99451}). Which other problems on three lists does the method make truly subquadratic? It solves 3SUM over F_p^d for every fixed prime p with 3XOR's exponents, and over every finite abelian group of exponent p^2, such as Z_4^d, in O(n^{1.99726}). For coordinatewise problems with a fixed relation P on every coordinate triple, a certified exhaustive computation shows that every Boolean P, and every functional P over three letters, either is the solution set of an equation over Z, F_2 or F_3, and the problem is then truly subquadratic, or has a gadget for Orthogonal Vectors, and the problem is then hard under the Orthogonal Vectors hypothesis. Over four letters, just four functional relations, up to symmetry, satisfy neither condition.

0.60

Product-Aware Deterministic Rounding for Quantized Matrix Multiplication

cs.LG cs.DScs.IT ·2026-09-11 ·Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal
similarity 0.62
Abstract · 30 pages, 7 figures

Scalar rounding decisions interact through matrix multiplication. We study deterministic product-aware rounding after scales, clipping bounds, and grids are fixed, with each active scalar choosing between adjacent levels. For dynamic activation rounding, null-space reduction preserves the relaxed product while leaving at most $r$ fractional decisions, where $r$ is the rank of the active gap-weighted weight block. Conditional-expectation completion gives a deterministic polynomial-time algorithm with squared product error at most $ \mathrm{OPT}_{\mathrm{dyn}}+rν_{\max}^2/4$, where $\mathrm{OPT}_{\mathrm{dyn}}$ is the best admissible error and $ν_{\max}$ is the largest row norm of that block. For reusable static weights, the exact expected product-loss metric is the uncentered input second moment with fixed output bias; free bias recalibration yields the centered covariance. Exact optimization is NP-hard even at rank one. In balanced blocks with $K=1024$ and $r=16$, conditional- expectation completion attains a dither-normalized median error of $0.010$, compared with $0.899$ for round-to-nearest. Clipping-aware initialization reduces median normalized error by a factor of $43.4$ at ten-percent clipping. Held-out Digits experiments show that retaining the input mean or correcting the output bias improves median product error over round-to-nearest in all four tested bit-width and calibration-size settings.

0.30