DFT 复杂度再降:O(n(log n)^0.99925) 打破 n log n 下界
generativist · x · 2026-10-10
OpenAI 官方社区项目 Problem #130 发布更新：团队宣布找到低于 n log n 的精确离散傅里叶变换（DFT）算法，新界为 T(n) = O(n(log n)^(1−δ))，其中 δ = 0.0007547360，比此前公布的 δ = 7.3×10⁻⁵ 的指数收益提升约 10.34 倍。
- 更强的傅里叶结果来自 Jacob Sussman 提出的五阶段框架与 Chafik Boukhalfa 的改进构造。
- 工作建立在 OpenAI、0xdoug、RohanArun、Swapnil Jain 等社区成员的贡献之上。
- 有评论戏称这是「真正的加速」——不过该渐近改进要到 n 约 10^600000 规模才能超过标准 O(n log n) 算法 1%，理论意义远大于实用价值。
「研究」频道最新
- 循环模型新方法:1.6B 模型用 1/3 KV 缓存追平全缓存基线 — rupspace · 2026-10-11
- 纯 RL 训出的机器人自创杆上立杆、原地翻螺母等人类不会教的策略 — KyleMorgenstein · 2026-10-11
- 用一个三分类例子讲透 Softmax 与交叉熵的分工与梯度 — techNmak · 2026-10-11
- PartLLM 登陆 SIGGRAPH Asia：LLM 驱动任意粒度 3D 网格部件分割 — Promptmethus · 2026-10-11
- Duo Bregman伪散度实现截断指数族KL散度闭式计算 — FrnkNlsn · 2026-10-11
- 26 模型 228 任务:METR 时间视界曲线 2-30 分钟段近乎平坦 — lulzxdxdxd · 2026-10-11