OpenAI 的 O(n^2.25) 快速矩阵乘法算法被推广至一般数域
aran_nayebi · x · 2026-10-08
有人将 OpenAI 团队的 O(n^{2.25}) 快速矩阵乘法(FMM)算法从复数域推广到了一般域,并在 Lean 中完成形式化验证。被引帖指出这篇新 FMM 论文出乎意料地优雅:不同于以往对 CW 张量做幂运算再裁剪的思路,它定义了张量上的势函数,通过研究简单的卷积张量以反证法完成整个证明。讨论者还认为 n^{9/4} 可能真就是矩阵乘法复杂度的正确指数;arapnayebi 补充称 SETH 或许是下一个被改进的方向,而 APSP 与 3SUM 此前的改进会带动其他归约问题的进步,且该矩阵乘法结果已被轻松推广。
所属事件:OpenAI 快速矩阵乘法算法证明被推广至任意域(2 条相关)→
「研究」频道最新
- 研究者实测:DinoV3 patch 默认编码位置信息过强,需清理再用 — StephanSturges · 2026-11-22
- 黎曼猜想 Lean 4 形式化挑战上线:追踪证明压缩与模型 agent 基准 — flngr · 2026-11-22
- Kalshi 预测市场:54% 押注 P vs NP 2030 年前被解决,概率跳涨 — ricklamers · 2026-11-22
- OpenAI 证明文档首现超线性电路下界,复杂度界仍难啃 — thomasahle · 2026-11-22
- 一张图测八款 VLA:仅 3 个答对,ERQA 基准遭质疑题目本身存疑 — giffmana · 2026-11-22
- 曙光8000十万卡集群斩获戈登·贝尔奖,异构节点性能达纯CPU三倍 — 智东西 · 2026-11-22