Rectangular matrix multiplication from polynomial products

Abstract

In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove $\omega (1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$, and $\omega (1,k,1)\le 1+k+\frac{1}{4k}$ for $k\ge \frac{1}{2}$. In particular, $\omega (1,\frac{1}{2},1)=2$ and the dual exponent satisfies $\alpha \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 $\omega (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.