我们给出了对3SUM和全对最短路径（APSP）的教科书算法的首次多项式改进：我们展示了如何确定性解决n个多项式大小整数上的3SUM，时间为O(n^{1.9992})，以及有向n顶点图上的APSP，权重为多项式有界整数，时间为O(n^{2.9995})。这反驳了3SUM和APSP假设。利用已知归约，我们还反驳了3SUM和APSP假设的实值版本、精确三角形假设、零权重k-Clique假设，以及van den Brand、Nanongkai和Saranurak的三个矩形提示在线矩阵-向量猜想，并为各种其他问题提供了多项式加速。所有这些结果都源于一个用于薄矩阵乘积的新算法。设X为N×D整数矩阵，Y为D×N整数矩阵，且D ≤ N^{1/18}，W为至多N^2/√D个位置的任意集合。我们计算条目(XY)[I, J]，(I, J)∈W，在O(N^2/D^{0.063})次操作内，这比写出XY或逐一计算N^2/√D个内积所需的时间多项式地少。我们通过修改Coppersmith矩形矩阵乘法算法的一个变体来设计此算法，该变体基于Schönhage的十乘法恒等式，仅执行W中条目所需的操作，并表明所需操作很少。作为图算法解释，这解决了稀疏倾斜三部图中的全边稀疏三角形问题，其中两部分有n个顶点，但一部分有n^{ε}个顶点，ε<0.12。通过已知归约，精确三角形，以及因此3SUM和APSP，归约到此问题。我们还给出了一个数据结构版本，用于回答预先未知的XY单个条目的查询。提交历史：来自Josh Alman [查看电子邮件] [v1]2026年10月5日星期一17:44:29 UTC（93 KB）
来源: Hacker News · 由HeadlinesBriefing整理摘要