跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.42012 · v2

3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized

首次提交 2026-10-31 00:49
版本更新 2026-11-15 02:36
雷达观测 2026-11-17 12:06
arXiv ↗PDF ↗

摘要

Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion--exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for kk-SUM for integer inputs for odd constant kk in O(n⌈k/2⌉−εk)O(n^{\lceil k/2\rceil-\varepsilon_k}) time for some constant εk>0\varepsilon_k>0, disproving the kk-SUM Hypothesis for all odd kk. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

作者备注:minor edits

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-15 02:36 · 最新观测版本

3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized

Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion--exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for kk-SUM for integer inputs for odd constant kk in O(n⌈k/2⌉−εk)O(n^{\lceil k/2\rceil-\varepsilon_k}) time for some constant εk>0\varepsilon_k>0, disproving the kk-SUM Hypothesis for all odd kk. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

查看此版本解读 →查看此版本原文 ↗