Recovery Beats Storage: Improved Space for Preprocessed 3SUM

Abstract

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^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ and a target set $C^{\prime }$ of size $O(n)$, by solving the 3SUM instance $(A^{\prime },B^{\prime },C^{\prime })$. Kirkpatrick, Kuszmaul, Mathialagan, and Vassilevska Williams [ICALP 2026] gave the first algorithm with subquadratic space for this problem, achieving $\tilde{O}(n^{3/2+\epsilon })$ query time using $\tilde{O}(n^{2-2\epsilon /3})$ space, for every $\epsilon \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)$ summing to 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, we recover them on demand by leveraging the Fiat--Naor data structure [SICOMP 1999] to invert the function $(a,b)\mapsto (a+b\mathrm{mod}p)$. This simplification improves the space bound to $\tilde{O}(n^{\max (2-\epsilon ,11/6-\epsilon /3)})$, while maintaining the same query time. Moreover, our construction is the first to achieve subquadratic space while supporting adaptively chosen queries.

16 pages, 5 figures