Real to integer reduction improves speed of 3SUM queries
Preprocessed 3SUM: From Reals to Integers
Data Structures and Algorithms
Summary
The Preprocessed 3SUM problem involves quickly checking if three numbers in a subset fit the equation a + b = c. The best algorithms for integer numbers are faster than those for real numbers. The authors developed a way to convert real numbers problems into integer ones without making queries slower, matching the speed of integer solutions. Their simple and clever approach uses tools from sparse linear algebra and could help with other similar math problems.
What this means in practice
- •For algorithm engineers: Improve algorithms that rely on fast 3SUM queries with real-number inputs by using integer-based techniques.
- •For computational geometry developers: Optimize geometric computations dependent on additive relations by reducing real number inputs to integer problems.
A theory result. No direct application yet.
Authors
Nick Fischer, Jonas Schmidt
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.