论文多源确认精选

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)。

原文 · arXiv: OpenAI

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.

产业坐标与信源核验

本条情报归属 AITOP「论文」核心栏目,重点聚焦北美前沿实验室与硅谷科技巨头。涉及核心实体与技术议题包括:矩阵乘法、ω指数、最短路径、arXiv,读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。

信源核验说明:本文原始信息发布自一手权威信源「arXiv: OpenAI」(Tier-1 一手发布),具备高确定性参考价值。截至目前,全网已有 11 家独立信源对该事件进行交叉印证与跟进报道(含 rohanpaul_ai、kimmonismus、宝玉 等),属于近期高关注度行业信号。