新论文推翻 3SUM 与 APSP 猜想，传 Claude 参与发现次二次算法
burny_tech · x · 2026-10-06
arXiv 新论文《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》（作者 Josh Alman、Virginia Vassilevska Williams）给出首个对教科书级算法的多项式改进：
- 3SUM 可在对数大小的整数上以 O(n^1.9992) 时间确定性地求解，APSP 可在多项式整数权重图上以 O(n^2.9995) 时间求解，直接推翻了 3SUM 与 APSP 猜想。
- 借助已知归约，实数版 3SUM/APSP 猜想、Exact Triangle 猜想、Zero-Weight k-Clique 猜想及三个 Online Matrix-Vector 猜想也被一并推翻，并对一系列其他问题带来多项式加速。
- 核心是细矩阵乘的新算法：对 N×D 与 D×N 的整数矩阵（D≤N^{1/18}），只需计算指定 N²/√D 个位置时，可用 O(N²/D^0.063) 次操作完成，做法是改造基于 Schönhage 十乘恒等式的 Coppersmith 矩形矩阵乘算法，只执行必要运算。
Mira Murati 转发并称「Claude found a subquadratic 3SUM algorithm」，暗示 Claude 在该结果中发现/参与，引发热议。
所属事件: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