CS Paper Radar

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

Isaac Rudich, Louis-Martin Rousseau

cs.CC ·submitted 2026-10-01 13:05 UTC · v1
publishedtheory

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.

DOI
10.5281/zenodo.23047900,

Closest papers

Nearest neighbours by meaning across the whole index.

Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of $ω\le9/4$

cs.CC ·2026-10-20 ·Rafael Pass
similarity 0.77
Abstract

We give a self-contained constructive proof that the matrix multiplication exponent satisfies $ω\le9/4$. In a recent breakthrough, OpenAI~\cite{original} established this bound in the model of exact scalar arithmetic over the complex numbers, using non-constructive arguments in Strassen's asymptotic spectral framework. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every $γ>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+γ})$ integer arithmetic operations. As an independent contribution, we develop a framework of \emph{polynomial packings}---methods for reducing many polynomial multiplications to fewer ones using linear operations. We isolate and generalize a construction of OpenAI~\cite{original} to obtain a simple packing, and show how packings can be composed to amplify their ``compression rate", which finally yields Strassen-like identities.

0.07

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

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

A simplified proof of polynomial improvements for 3SUM and APSP

cs.CC ·2026-10-11 ·Sankeerth Rao Karingula, Shachar Lovett
publishedhot directionhighly cited similarity 0.71
Abstract

We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Schönhage's inner/outer-product identity, we construct a multiplication rule that shares intermediate products among many outputs. We apply this rule recursively and bound the work by counting the requested entries at each level. Applied to incidence matrices, the algorithm solves Offline Set Disjointness over a small universe. Known deterministic reductions then yield truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs.

0.58

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.70
Abstract · 18 pages. Kernel-only Lean proof: https://github.com/tejasvi/rank333-f2-kernel (archived at https://doi.org/10.5281/zenodo.23304899). Lean p…

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

0.22

Fast matrix multiplication via recursive $\langle$ 4x4x4:48 $\rangle$ algorithms into practice

cs.SC ·2026-09-10 ·Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic, Joshua Stapleton, Petr Tichavský
similarity 0.69
Abstract

We present a fast algorithm for multiplying two 4x4 matrices using 48 multiplications and 204 other operations (addition, subtraction or scaling by a constant) over any ring containing an inverse of 2. Applied recursively, this algorithm reaches a cost bound with leading term (7+3/8)n^{\log_4(48)}. Alternative basis decompositions of this algorithm further reduce this to (6+13/32)n^{\log_4(48)}, with square change of bases, and then to (5+2/3)n^{\log_4(48)}, using rectangular encodings with inner dimensions 24 and 32. The conversion costs of these alternative basis variants are included as lower-order terms.

0.24

Part of the Strassen algorithm can speed up matrix multiplication in a parallel pebbling game

cs.DC ·2026-10-06 ·Aaron Dayton, Thomas E. Baker
code/data similarity 0.67
Abstract · 18 pages, 10 figures

We present a novel variant of the Strassen algorithm called the Partial Strassen algorithm, which uses a fraction of the Strassen steps to perform matrix multiplication in less time than traditional implementations. The memory footprint required to implement this algorithm is provably small whether used with a single thread or in a multi-threaded context. Data comparing the Partial Strassen algorithm at depths one, two, and three with BLAS matrix multiplication show that the three-level Partial Strassen algorithm is able to perform matrix multiplication in $80\%$ the time of BLAS with $2.25$ times the memory requirement, with a theoretical improvement of $75\%$ for sufficiently large matrices. The Partial Strassen algorithm is also compared against an implementation of the traditional Strassen algorithm, and is shown to be more performant with increasing matrix size due to decreased memory consumption. An open source implementation of the Partial Strassen algorithm for arbitrary depth and rectangular matrix multiplication is also included.

0.42

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

A 52-Addition, Rank-23 Scheme for Exact 3 x 3 Matrix Multiplication

cs.DS ·2026-09-06 ·Hugo Nielsen
similarity 0.66
Abstract

We present a rank-23 algorithm for general 3 x 3 matrix multiplication using 52 additions or subtractions, together with a Karstadt-Schwartz-style basis change [1, 2]. This gives, to the best of our knowledge, a new best-known candidate for the addition-minimization problem for rank-23 general 3 x 3 matrix multiplication.

0.50