2026-07-20T15:08:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26515 2026-07-01T07:16:13Z ddc:004 open_access

Preprocessed 3SUM for Unknown Universes with Subquadratic Space Kirkpatrick, Yael Kuszmaul, John Mathialagan, Surya Vassilevska Williams, Virginia Graph Algorithms Diameter Distance Oracle Approximation Algorithm We consider the classic 3SUM problem: given sets of integers A, B, C, determine whether there is a tuple (a, b, c) ∈ A × B × C satisfying a + b = c. The 3SUM Hypothesis, central in fine-grained complexity, states that there does not exist a truly subquadratic time 3SUM algorithm. Given this long-standing barrier, recent work over the past decade has explored 3SUM from a data structural perspective. Specifically, in the 3SUM in preprocessed universes regime, we are tasked with preprocessing sets A, B of size n, to create a space-efficient data structure that can quickly answer queries, each of which is a 3SUM problem of the form A', B', C', where A' ⊆ A and B' ⊆ B. A series of results have achieved Õ(n²) preprocessing time, Õ(n²) space, and query time improving progressively from Õ(n^{1.9}) [Timothy M. Chan and Moshe Lewenstein, 2015] to Õ(n^{11/6}) [Timothy M. Chan et al., 2023] to Õ(n^{1.5}) [Kasliwal et al., 2025]. Given these series of works improving query time, a natural open question has emerged: can one achieve both truly subquadratic space and truly subquadratic query time for 3SUM in preprocessed universes? We resolve this question affirmatively, presenting a tradeoff curve between query and space complexity. Specifically, we present a simple randomized algorithm achieving Õ(n^{1.5 + ε}) query time and Õ(n^{2 - 2ε/3}) space complexity. Furthermore, our algorithm has Õ(n²) preprocessing time, matching past work. Notably, quadratic preprocessing is likely necessary for our tradeoff as either the preprocessing or the query time must be at least n^{2-o(1)} under the 3SUM Hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yael Kirkpatrick and John Kuszmaul and Surya Mathialagan and Virginia Vassilevska Williams 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.126 urn:nbn:de:0030-drops-265158 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.126 eng https://creativecommons.org/licenses/by/4.0/legalcode