CS Paper Radar

Polynomial Separation of a Shared Tensor Leg and Matrix Multiplication in Arbitrary Characteristic

Houxi Lü

cs.CC ·submitted 2026-10-12 13:34 UTC · v1
theory

Abstract

We improve the shared-leg separation construction in Proposition 3.1 of OpenAI, *An Upper Bound of $9/4$ for the Matrix Multiplication Exponent* (October 2, 2026). If $M$ tensor blocks have a common first space and independent matched sectors on their other two spaces, then $M+n-1$ copies of their matched sum degenerate to the full direct sum of the blocks, each tensored with an $n$-dimensional dot product. For $n=M$, this reduces the number of source copies from $5M$ to $2M-1$. The construction uses polynomial interpolation and truncated local substitution, with no roots of unity or factorial denominators. It works over every field containing enough distinct elements. We verify that the remaining spectral and discrete-growth arguments of the cited preprint are independent of characteristic. Over an algebraic closure, the replacement therefore gives $ω\leq9/4$ in every characteristic.

Closest papers

Nearest neighbours by meaning across the whole index.

Tensor value and the 9/4 bound for matrix multiplication

cs.CC math.RT ·2026-11-06 ·Mahmut Levent Doğan, Vladimir Lysikov, Keiya Sakabe, Michael Walter
theory similarity 0.73
Abstract

We give an exposition of OpenAI's recent result that the exponent of matrix multiplication is at most 9/4 valid over every field. Our main tool is a fractional symmetrized variant of the tensor value introduced by Coppersmith and Winograd, used in place of spectral points (tensor characters) in the original proof. We prove a superadditivity inequality for a power of this value on partially direct sums, whose summands share one tensor factor and occupy independent subspaces in the other two. Together with the degenerations of polynomial multiplication tensors from the OpenAI proof, this inequality yields the bound.

0.08

Semidirect sums of tensors and the matrix multiplication exponent

cs.CC cs.DS ·2026-11-03 ·Baitian Li
position similarity 0.67
Abstract · 31 pages, 1 figure

This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.

0.23

Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition

cs.SC cs.CC ·2026-09-11 ·Abhinav Agarwal
theoryhot direction similarity 0.64
Abstract

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

0.25

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

cs.CC ·2026-10-20 ·Rafael Pass
similarity 0.63
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

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.62
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

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

A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$

cs.CC cs.DS ·2026-09-06 ·Chengu Wang
theory similarity 0.60
Abstract

We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower bounds for restrictions of the first input constrain how many first factors of a decomposition can lie in each subspace. For a hypothetical $20$-term decomposition, the strengthened restriction bounds force all first factors of matrix rank at least two into a single coset of a three-dimensional rank-one subspace. An exhaustive computation finds no admissible first-factor profile with $20$ terms. We also prove that $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ has rank exactly $15$: three profiles with $14$ terms survive the corresponding computation up to symmetry, and short restriction arguments exclude them. We combine Wang's automated framework for tensor-rank lower bounds with D'Ambrosio's capacity-and-profile strategy. Our computational contributions are rank-one-span searches that strengthen the subspace lower-bound table and a direct, symmetry-reduced profile enumerator that enforces all subspace capacities simultaneously.

0.28

A lower bound for $\langle 3,2,m \rangle$ matrix multiplication

cs.CC cs.DS ·2026-09-18 ·Askar Tsyganov, Uliana Parkina, Sergey Samsonov, Maxim Rakhuba
theorycode/data similarity 0.59
Abstract

We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$. In particular, every exact bilinear algorithm for multiplying a $3\times 2$ matrix by a $2\times 5$ matrix requires at least $25$ multiplications. Together with the Hopcroft-Kerr upper bound, this proves that the $\langle 3,2,5\rangle$ matrix multiplication tensor has rank exactly $25$. The proof has been formally verified in Lean 4, with the formalization available at https://github.com/fallnlove/mm325_proof.

0.25