(min,+) 矩阵乘法指数再降，新算法改进 Anthropic 突破结果

thegautamkamath · x · 2026-10-17

理论计算机科学家 Gautam Kamath 在讨论近期简化证明的论文时，点名了 Barna Saha 与 Christopher Ye 的新论文《Simple, Faster (min, +) Matrix Multiplication and APSP》（arXiv:2610.20297）：该文给出确定性算法，在多项式有界整数输入下以 Õ(N^2.9964) 时间计算 (min,+)-矩阵乘积，改进了 Alman 与 Vassilevska Williams（论文中标注为 Anthropic 相关的 2026 突破）给出的 O(N^2.9995) 指数，并由此得到更简洁模块化的真正亚立方 APSP 算法。

Kamath 同时坦言：圈内有人私下认为原帖中部分「简化」论文简化并不实质、写作仍有瑕疵，但他乐见这一方向的努力，并表彰了多位在「不光鲜」问题上扎实工作的作者。