最近，Anthropic 在 3SUM 与全点对最短路（APSP）上取得了真正的次二次和次立方算法，这些算法依赖于对矩形矩阵乘法的特定输出条目的新子例程，后者通过改造 Schönhage (1981) 与 Coppersmith (1982) 的技术得到。\ \ 本文提供了三项主要贡献：\
- 对整数输入的 3SUM，给出一种全新的随机化次二次算法。该算法不使用矩阵乘法，而是改写了子集卷积和 ζ 变换的动态规划实现，只依赖包含-排除的简单减法技巧，甚至不需要快速傅里叶变换，整体思路约五页即可完整呈现。\
- 将相同思路推广到奇数常数 $k$ 的 $k$‑SUM，得到时间复杂度 $O\bigl(n^{\lceil k/2\rceil-\varepsilon_k}\bigr)$（其中 $\varepsilon_k>0$ 为常数），从而否定了所有奇数 $k$ 的 $k$‑SUM 假设。\
- 先前从 3SUM 与 APSP 到选定条目矩形矩阵乘法的归约在实数输入下是随机化的。我们构造了全新的确定性归约，进而得到实数 3SUM 的真正次二次确定性算法以及实数 APSP 的真正次立方确定性算法。\ \ 点评