CS Paper Radar

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

Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu

cs.DS ·submitted 2026-10-30 16:49 UTC · v1

Abstract

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 $k$-SUM for integer inputs for odd constant $k$ in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant $\varepsilon_k>0$, disproving the $k$-SUM Hypothesis for all odd $k$. 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.

Closest papers

Nearest neighbours by meaning across the whole index.

A simplified proof of polynomial improvements for 3SUM and APSP

cs.CC ·2026-10-11 ·Sankeerth Rao Karingula, Shachar Lovett
publishedhot directionhighly cited similarity 0.72
Abstract

We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Schönhage's inner/outer-product identity, we construct a multiplication rule that shares intermediate products among many outputs. We apply this rule recursively and bound the work by counting the requested entries at each level. Applied to incidence matrices, the algorithm solves Offline Set Disjointness over a small universe. Known deterministic reductions then yield truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs.

0.58

Simple, Faster (min, +) Matrix Multiplication and APSP

cs.DS ·2026-10-14 ·Barna Saha, Christopher Ye
theory similarity 0.70
Abstract · 17 pages

In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.

0.44

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

cs.DS cs.CC ·2026-10-05 ·Josh Alman, Virginia Vassilevska Williams
highly cited similarity 0.67
Abstract · 76 pages

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

0.51

Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering

cs.DS cs.DB ·2026-10-07 ·Mihail Stoian
hot direction similarity 0.66
Abstract · Feedback welcome; v2: fixed technique naming

We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.

0.27

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

cs.CC ·2026-10-01 ·Isaac Rudich, Louis-Martin Rousseau
publishedtheory similarity 0.64
Abstract

Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.

0.19

A Note on Truly Subquadratic Time FPTAS for Knapsack

cs.DS ·2026-11-17 ·Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
similarity 0.64
Abstract

We show that an $\widetilde{O}(m^ρ)$-time algorithm for integer $(\min,+)$-convolution, where $1<ρ<2$, gives a randomized fully polynomial-time approximation scheme for $0$--$1$ Knapsack running in $\widetilde{O}(n+(1/ε)^{1+ρ/2})$ time. The algorithm returns a feasible solution whose profit is at least the optimum divided by $1+ε$, with high probability. We use the all-capacities proximity decomposition of Chen, Lian, Mao, and Zhang. Its two quadratic computations are replaced by blocked computation of requested prefix and suffix functions, and exact computation within groups sharing one of Chan's profit grids. Thus the approximation scheme retains half of the saving in the convolution exponent. Wang's weighted-cache 3SUM bound, transferred to witnessed integer convolution by Zhou, gives the numerical bound $\widetilde{O}(n+(1/ε)^{1.981})$.

0.21

A Fast Algorithm for Subspace Convolution

cs.DS cs.CC ·2026-11-09 ·Shlomo A. Perles, Omri Weinstein
theorycode/data similarity 0.64
Abstract · 35 pages, 2 figures. Code, experiments, and Lean 4 formalizations: https://github.com/shlomi-perles/subspace-convolution

A cornerstone result in Boolean lattice theory is the subset-zeta transform, which computes the $f$-weighted subset summation problem $(Z f)(B)=\sum_{A\subseteq B}f(A)$ for all $ B\subseteq[n]$ in $O(N \log N)$ additions instead of the naïve $O(3^n) = O(N^{\log_2 3})$, where $N=2^n$. This paper studies the algebraic analogue of this problem--the subspace summation problem--where subsets are replaced by linear subspaces in $\mathbb{F}_q^n$. Surprisingly, we show that this problem admits a similar $Θ_q(N_q \log N_q)$-time algorithm, where $N_q$ is the number of subspaces. This improves substantially (in both theory and practice) over lattice-based algorithms ([BHK+16, KKW16]), which are known to be optimal for addition-only algorithms over $\mathbb R$. We prove similar runtimes for inversion, rank-constrained sums and span convolution. We describe two main applications: Fast linear algebra on Grassmann graphs: Matrix--vector multiplication for arbitrary distance-invariant kernels on $N$-vertex Grassmann graphs in $O_q(N\log N)$ arithmetic operations, together with fast spectral projections and exact solutions of the corresponding linear systems. Graph coloring of low binary cut-rank graphs: An $n^{2^{r^2/4+O(1)}}$-time algorithm for computing the chromatic number and chromatic polynomial of an $n$-vertex graph, given a rank-decomposition of width $r$. We also give quantitative reductions from satisfiability and monotone constraint problems. Experiments show speedups in measured running time of up to $18$ over the covering-pair algorithm for the zeta transform, $190$ over Poisson summation for rank-constrained sums, and $22$ over the distance-matrix recurrence for Grassmann kernel multiplication. Lean 4 formalizations of the transform identities, arithmetic operation bounds, and graph-coloring constructions accompany the paper [PW26].

0.28

Real-to-Integer Reduction for All-Pairs Shortest Paths

cs.DS ·2026-11-03 ·Nick Fischer, Adam Polak, Jonas Schmidt
theory similarity 0.62
Abstract

Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current techniques, or are the real-valued variants inherently harder? One way to study this question is through real-to-integer reductions. We give (randomized, combinatorial) subcubic real-to-integer reductions for two central graph problems in fine-grained complexity: All-Pairs Shortest Paths and Exact Triangle. That is, we show that if the integer variants of these problems can be solved in truly subcubic time, then the real variants can also be solved in truly subcubic time. Our work extends and combines techniques from three previous works: (1) our real-to-integer reduction for the 3SUM problem (Fischer, Polak, Schmidt, FOCS 2026), which itself combines the Frank--Tardos theorem from optimization with Freiman's theorem from additive combinatorics; (2) universe reduction for APSP (Fischer, STOC 2026), which we generalize to reals and use to reduce the doubling of the set of edge weights; and (3) the ``Fredman's trick meets dominance product'' technique (Chan, Vassilevska Williams, Xu, STOC 2023), which is needed to adapt the prior real-to-integer framework from equality constraints to inequalities. As a corollary, our reduction combined with Yuval's fast Integer APSP algorithm in the real RAM model with multiplication (IPL 1976) shows that the Real APSP Hypothesis is false in this model, which also follows from the very recent breakthrough by Alman and Vassilevska Williams using a very different approach.

0.05