Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-281 | 27th October 2026 13:02

Exposition of OpenAI’s Matrix Multiplication in Exponent 9/4 (and an explicit algorithm)

RSS-Feed




TR26-281
Authors: Amir Shpilka
Publication: 27th October 2026 13:03
Downloads: 174
Keywords: 


Abstract:

A recent manuscript of OpenAI proves that the exponent of matrix multiplication satisfies $\omega\le9/4$. We give an elementary, self-contained proof of this bound. We follow the ideas of the original manuscript, but implement them differently to obtain explicit algorithms. Specifically, for every $\varepsilon>0$, we give a matrix multiplication algorithm with exponent below $9/4+\varepsilon$ and base matrix size at most $2^{(1/\varepsilon)^{O(1)}}$.

We also show that techniques similar to those used in the square case apply to rectangular matrix multiplication. Starting from Strassen's tensor, we give elementary proofs of the bounds $\omega\bigl(1,\frac{2}{3\log 3},1\bigr)=2$ and $\omega(1,0.539,2)=3$. Stronger rectangular bounds are known, but we include these proofs for their simplicity.

In an appendix we describe the original proof, which goes through Strassen's theory of the asymptotic spectrum.



ISSN 1433-8092 | Imprint