CS Paper Radar

Preprocessed 3SUM: From Reals to Integers

Nick Fischer, Jonas Schmidt

cs.DS ·submitted 2026-10-15 14:22 UTC · v1

Abstract

The Preprocessed 3SUM problem asks to preprocess a set $A$ of $n$ numbers so that we can quickly decide whether a query subset $A' \subseteq A$ contains a solution $a+b=c$. The best known query bounds differ substantially between integer and real inputs. For integers, a series of advances with near-quadratic preprocessing reduced the query time from $\tilde O(n^{13/7})$ [Chan, Lewenstein; STOC '15] to $\tilde O(n^{11/6})$ [Chan, Vassilevska W., Xu; STOC '23], and finally to $\tilde O(n^{3/2})$ [Kasliwal, Polak, Sharma; SOSA '25]. For reals, only the first of these bounds has been achieved, by adapting the corresponding integer algorithm [Fischer; SODA '25]. Is this gap inherent to the more limited tools available for real inputs? We give a randomized real-to-integer reduction with $\tilde O(n^2)$ preprocessing overhead and no asymptotic increase in query time. This yields $\tilde O(n^2)$ preprocessing and $\tilde O(n^{3/2})$ query time for real inputs, closing the gap. We show how to extend our result to the setting where one set is unknown at preprocessing time. Our reduction is conceptually simple, and relies on an interesting technical toolkit around old and new tools from sparse linear algebra. More broadly, it suggests a route to real-to-integer reductions for other additive problems.

Closest papers

Nearest neighbours by meaning across the whole index.

Recovery Beats Storage: Improved Space for Preprocessed 3SUM

cs.DS ·2026-08-23 ·Amir Carmel, Yakov Kosoburd, Robert Krauthgamer
similarity 0.72
Abstract · 18 pages, 4 figures

The 3SUM problem asks, given sets $A,B,C$ of integers, whether there exist $a\in A$ and $b\in B$ whose sum belongs to $C$. In the preprocessed variant with unknown $C$, one preprocesses sets $A$ and $B$, each of size $n$, and subsequently answers a query specified by subsets $A'\subseteq A$, $B'\subseteq B$ and a target set $C'$ of size $O(n)$, by solving the 3SUM instance $(A',B',C')$. Kirkpatrick, Kuszmaul, Mathialagan, and Vassilevska Williams [ICALP 2026] gave the first algorithm with subquadratic space for this problem, achieving $\widetilde{O}(n^{3/2+ε})$ query time using $\widetilde{O}(n^{2-2ε/3})$ space, for every $ε\in[0,1/2]$. Their algorithm employs separate mechanisms for heavy and light targets, and for each heavy target it stores explicitly the list of pairs $(a,b)$ whose sum is congruent to it modulo a random prime $p$ but differs from it. These lists dominate the space bound. We present a unified construction that uses a single mechanism for all queries. Instead of storing these lists of pairs, our algorithm recovers on demand the residue class of the target modulo a random prime by inverting the function $(a,b)\mapsto (a+b\bmod p)$. Additionally, instead of storing the heavy targets, it recomputes at query time a set that covers them. This leads to an improved space bound of $\widetilde{O}(n^{2-ε})$, while maintaining the same query time. Moreover, our construction is the first to achieve subquadratic space while supporting adaptively chosen queries.

0.49

3SUM Is Really Hard: A Real-to-Integer Reduction

cs.DS ·2026-10-07 ·Nick Fischer, Adam Polak, Jonas Schmidt
top venuetheory similarity 0.67
Abstract · To appear in FOCS 2026

We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an open problem posed by Chan, Vassilevska Williams, and Xu [STOC 2022], and constitutes the first such tight real-to-integer self-reduction in fine-grained complexity. Our proof relies on a surprising combination of the Frank--Tardos theorem from optimization with Freiman-type theorems from additive combinatorics.

0.71

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

cs.DS ·2026-11-03 ·Nick Fischer, Adam Polak, Jonas Schmidt
theory similarity 0.67
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

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.63
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.08

Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis

cs.DS ·2026-10-22 ·Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki
top venuetheory similarity 0.62
Abstract · 66 pages, 2 figures, published in FOCS 2026

The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n)}$, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).$M$. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).$M^{1/3}$. In this work, we give the first poly(n).$M^{o(1)}$-time algorithm for Equal Subset Sum in the regime $M = 2^{o(n)}$. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when $M = Θ(2^{n})$: a poly(n)$\cdot 2^{n/4}$-time algorithm in the average case.

0.32

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

cs.DS cs.DB ·2026-10-07 ·Mihail Stoian
hot direction similarity 0.61
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

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

cs.DS ·2026-10-30 ·Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu
similarity 0.58
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.

0.34

Finding Integer Roots of Polynomials in Nearly Optimal Time

cs.DS math.NTcs.SC ·2026-11-03 ·Yansong Feng, Itamar Nir
theory similarity 0.58
Abstract

Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde O(nb)$ whenever $b\leq n^{1/4}$. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for $b\leq n^{1/4}$. The fastest previous deterministic algorithm, due to Nir, takes $\widetilde O(n^{3/2}b)$ bit operations and works only for square-free polynomials. Instead of $p$-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top $\min(n,b)+1$ coefficients of $f$. Every integer root $r$ of $f$ with $|r|\geq 2$ lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of $O(\min(n,b))$ candidate integers that is guaranteed to contain all integer roots of $f$. Although a single candidate can have up to $b$ bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in $\widetilde O(nb)$ bit operations.

0.21