arXiv 论文将 OpenAI 矩阵乘法分析推广到矩形乘积，证明 α≥1/2
Rectangular matrix multiplication from shared-leg entropy
有人把 OpenAI 那篇矩阵乘法论文的方法推到矩形情形，证明 α≥1/2，最短路径算法直接降到 O(n^2.5)，做理论算法的可以看看证明思路。
一篇 arXiv 论文将 OpenAI 近期矩阵乘法结果所用的共享腿熵不等式推广到矩形乘积，证明当 k≥1/2 时 ω(1,k,1)≤1+k+1/(4k)，并给出 ω(1,1/2,1)=2 与对偶指数 α≥1/2。作者保留了双腿对称性与各扇区方向，通过幂化辅助剖面的渐近斜率得出谱约束 b≤4a(1-a)，再经张量谱对偶得到矩形曲线。应用方面，Zwick 的有向无权图全对最短路径算法运行时间降至 O(n^2.5)，结合 Alman 与 Vassilevska Williams 的 (min,+)-乘积改进可进一步达到 O(n^2.4999)。
Rectangular matrix multiplication from shared-leg entropy
In this note, we extend the analysis underlying a recent matrix-multiplication result by OpenAI to rectangular products and prove that $ω(1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$ and $ω(1,k,1)\le 1+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}$. We use the shared-leg entropy inequality and polynomial-multiplication degenerations from that work, retaining two-leg symmetry and the orientation of each sector. Logarithmic averaging produces homogeneous auxiliary profiles. Their powered versions have a common asymptotic slope, and bounding their intercepts gives the spectral constraint $b\le 4a(1-a)$. This yields the rectangular curve by tensor-spectrum duality. 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.
