Alman 与 Williams 突破数十年瓶颈：3SUM 首次达到亚二次复杂度
auto_grad_ · x · 2026-10-06
Josh Alman 与 Virginia Vassilevska Williams 发布新论文，首次对教科书级经典算法给出多项式级改进：对 n 个多项式大小的整数，3SUM 可在 O(n^1.9992) 时间内确定性求解；带多项式界整数权重的有向图 APSP 可在 O(n^2.9995) 时间内求解。这一结果直接推翻了 3SUM 假设与 APSP 假设——这两个假设是细粒度复杂度理论的基石，此前被广泛认为不可攻破。\n\n借助已知归约，论文还推翻了实数版 3SUM/APSP 假设、Exact Triangle 假设、零权 k-Clique 假设等多个重要猜想，并给一系列问题带来多项式加速。核心技术是单一的新「薄矩阵乘」算法：对 N×D 与 D×N 的整数矩阵（D≤N^1/18），只需输出任意 N²/√D 个指定位置时，可在 O(N²/D^0.063) 次运算内完成，比逐个计算这些内积更快——其构造基于 Schönhage 的十次乘法恒等式改造 Coppersmith 矩形矩阵乘算法。
所属事件:Alman 与 Williams 首破 3SUM 与 APSP 平方/立方下界(6 条相关)→
「研究」频道最新
- Cohere 发布 Tiny Aya 多语言小模型家族，支持 70 余种语言 — Cohere_Labs · 2026-10-06
- 当 AI 改写 O(n²):优雅数学定理会被 LLM 逐一打破吗 — teortaxesTex · 2026-10-06
- ETH 团队 AME-2 四足步态论文被 TRO 接收,开源 G1 训练代码库 — ChongZzZhang · 2026-10-06
- 0.8B 模型闭式权重手术跑赢 2B 模型，ARC-Challenge 达 42.15% 零反向传播 — AdventurousTwo6445 · 2026-10-06
- MIT 团队发布科学任务分类法:覆盖 232 子领域、20.8 万项任务 — JMateosGarcia · 2026-10-06
- 把 Transformer 蒸馏进循环架构：固定记忆实现线性复杂度机器人记忆 — chriswolfvision · 2026-10-06