Recovery Beats Storage: Improved Space for Preprocessed 3SUM
Amir Carmel, Yakov Kosoburd, Robert Krauthgamer
原文摘要
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.
cs.DS