CS Paper Radar

Multiplying matrices via polynomials: exposition and barriers

Alimzhan Amanov, Maxim van den Berg, Jeroen Zuiddam

cs.CC math.RAmath.RT ·submitted 2026-10-21 17:15 UTC · v1
highly cited

Abstract

We give an exposition of OpenAI's recent proof that the exponent $ω_\mathbb{C}$ of matrix multiplication over the complex numbers satisfies $ω_\mathbb{C}\leq9/4$. Our version of the proof gives $ω_\mathbb{F}\leq9/4$ over every field $\mathbb{F}$. We also treat the rectangular matrix multiplication exponent $ω_\mathbb{F}(a,b,c)$. Here we have $ω_\mathbb{F}(1,k,1)=2$ for $0\leq k\leq1/2$ and $ω_\mathbb{F}(1,k,1)\leq1+k+1/(4k)$ for $k\geq1/2$, and, for real numbers $a\geq b\geq c\geq0$, $ω_\mathbb{F}(a,b,c)=a+b$ if $c(a+b)\leq ab$ and $ω_\mathbb{F}(a,b,c)\leq(a+b+c)/2+(ab/c+ac/b+bc/a)/4$ otherwise. Our exposition is in the language of degeneration inequalities among polynomial multiplication tensors and Strassen's asymptotic spectrum duality. We moreover prove an operational barrier (which can be thought of as coming from an operational asymptotic spectrum) showing that the current analysis of all these upper bounds on $ω_\mathbb{F}$ and $ω_\mathbb{F}(a,b,c)$ is optimal and that in fact the current degeneration ingredients cannot improve the bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

Rectangular matrix multiplication from polynomial products

cs.DS ·2026-10-07 ·Przemyslaw Uznanski
theoryhighly cited similarity 0.70
Abstract

In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove $ω(1,k,1)\le2$ for $0\le k\le\frac{1}{2}$, and $ω(1,k,1)\le1+k+\frac{1}{4k}$ for $k\ge\frac{1}{2}$. In particular, $ω(1, \frac{1}{2},1)=2$ and the dual exponent satisfies $α\ge\frac{1}{2}$. The proof uses explicit degenerations of convolution tensors, multinomial counting, and Strassen's spectral theorem. An angular constraint on three dot-product parameters gives both the rectangular curve and a bound for $ω(a,b,c)$. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.

0.54

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

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

Semidirect sums of tensors and the matrix multiplication exponent

cs.CC cs.DS ·2026-11-03 ·Baitian Li
position similarity 0.52
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

An $m^{2.943}$ Bohnenblust--Hille Bound on the Boolean Cube

cs.IT math.APmath.CA ·2026-09-17 ·Joseph Slote, Chun-Kai Tseng, Alexander Volberg
similarity 0.52
Abstract · 31 pages

Let $q_m=2m/(m+1)$ and put \[ β_0=\frac{3}{2}+\frac{1}{\log 2}=2.9426950408\ldots, \] where $\log$ is the natural logarithm. We give a proof scheme showing that, for every $\varepsilon>0$, there is $C_\varepsilon<\infty$ such that every complex-valued function $f:\{-1,1\}^n\to\C$ of Fourier degree at most $m$ satisfies \[ \left(\sum_{A\subseteq[n]}\abs{\wh f(A)}^{q_m}\right)^{1/q_m} \le C_\varepsilon m^{β_0+\varepsilon}\norm{f}_\infty. \] The improvement over the $m^9$ estimate of the earlier draft has two ingredients. The first three Fourier levels are estimated at the scales $m$, $m^{3/2}$, and $m^{5/3}$. These losses are encoded in the weight $M^{μ_r/r}r^B\min\{r,L_M\}^8$, $L_M\asymp_B \log (M+1)$, with $μ_r=\lceil3r/2\rceil$ for $r\ge2$. A parity-compatible central window handles $r<L_M$, while a shrinking balanced window handles $r\ge L_M\asymp_B\log(M+1)$, no parity is used in this regime. The leading high-degree loss--gain factor is $\ee\,2^{-B}$; careful uniform bounds close the bootstrap for every $B>1/\log2$. The formula for $μ_r$ is explained below.

0.58

The APN Property of Two Families of functions over $\F_{2^{n}}$ from the Switching Construction

cs.IT ·2026-11-03 ·Chenmiao Shi, Longjiang Qu, Kangquan Li
theory similarity 0.51
Abstract

Let $m\geq5$ be odd with $3\nmid m$. Helleseth, Ichanska, and Kaleyski \cite{HIK} conjectured that two norm-perturbed Budaghyan--Helleseth--Kaleyski functions $F_2,F_3$ over $\F_{2^{2m}}$ are APN. In this paper, we prove this conjecture. First, by using the basis $(1,β)$ of $\F_{2^{2m}}$ over $\F_{2^m}$, we show that $F_2$ and $F_3$ are EA-equivalent to two functions $\mathcal G_1$ and $\mathcal G_0$, respectively. Their derivatives can be written as two trace equations for a matrix $P\in\mathrm{GL}(2,\F_{2^m})$. We then prove that these two equations have no solution. The proof uses only identities over finite fields, the characteristic polynomial of a $2\times2$ matrix, and elementary properties of Frobenius automorphisms. The repeated-root case and all parity cases are considered separately. It follows that the derivative of each function has kernel of size two in every nonzero direction, and hence both $F_2$ and $F_3$ are APN for every admissible $m$.

0.30

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

cs.CC ·2026-10-12 ·Houxi Lü
theory similarity 0.51
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.

0.46

Lossless Hardness Condensation in Deterministic Communication Complexity

cs.CC ·2026-09-23 ·Simon Mackenzie
theory similarity 0.50
Abstract · 33 pages, 8 figures

A communication problem can have far more possible inputs than its communication cost would suggest. Must its difficulty already be present on a much smaller set of inputs? We prove that every finite total Boolean matrix of deterministic communication complexity $c\ge4$ has a submatrix on $2^k$ of its original rows and $2^k$ of its original columns, with $k=Θ_\varepsilon(c)$ and complexity at least $(1-\varepsilon)(k+1)$, for every fixed $0<\varepsilon<1$. Since $k+1$ is the maximum possible cost on such a square, the retained problem can be arbitrarily close to maximally hard. This answers affirmatively the lossless condensation question of Hamed Hatami; Göös, Newman, Riazanov, and Sokolov (STOC 2024), who recorded it as Open Problem 2, conjectured a negative answer. Hrubeš previously guaranteed input length $Ω(\sqrt c)$. The same argument gives an original $2^{c-2}$-by-$2^{c-2}$ square retaining at least $c/3-O(\log c)$ bits of communication complexity. The proof builds on Hrubeš's counting and covering argument. We count submatrices equipped with short communication protocols: a player names a covering submatrix, then the players run its protocol. This avoids the loss from converting rectangle partitions into protocols. A recursion on rectangles makes the argument constructive. For fixed rational $\varepsilon$ and any target depth $d\ge4$, a deterministic algorithm returns either a protocol of depth below $d$, or a square of original inputs at input length $Θ_\varepsilon(d)$ with the same near-maximal guarantee. Its running time is $2^{O(2^d)}$ times a polynomial in the table size. If the original complexity is at least $d$, the algorithm necessarily returns the square. An extension gives constant-factor condensation for any fixed number of number-in-hand players, with bounds independent of the finite output alphabet.

0.23

Small sums of roots of unity: polylogarithmic exceptional sets and conditional separation

cs.CC math.NT ·2026-10-19 ·Qi Cheng
theory similarity 0.50
Abstract

We prove a polylogarithmic exceptional-set estimate for symmetric five-term sums of roots of unity of arbitrary order. More precisely, at most $O((\log(2N))^{11})$ points of the $N$-grid satisfy $|1+2\cos(2πx)+2\cos(2πy)|<\exp(-C(\log(2N))^{13})$. This implies the corresponding bound for small conjugates at the reduced conductor: outside polylogarithmically many real embeddings, every such sum is at least quasipolynomially large. The proof is unconditional and combines a polynomial-vector-field multiplicity estimate, arithmetic jet determinants, analytic propagation, and interpolation determinants for nearby grid points. As a companion result, assuming a uniform number-field $abc$ conjecture, we prove that every sum of a fixed number of distinct prime-order roots of unity has modulus at least $\exp(-\varepsilon p)$ for every $\varepsilon>0$ and all sufficiently large primes $p$, uniformly in the exponents. That proof uses simultaneous compression of the exponents, discriminant estimates, and cyclic resultants.

0.34