DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.126

Preprocessed 3SUM for Unknown Universes with Subquadratic Space

Authors: Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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 Õ(n²) preprocessing time, Õ(n²) space, and query time improving progressively from Õ(n^{1.9}) [Timothy M. Chan and Moshe Lewenstein, 2015] to Õ(n^{11/6}) [Timothy M. Chan et al., 2023] to Õ(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 Õ(n^{1.5 + ε}) query time and Õ(n^{2 - 2ε/3}) space complexity. Furthermore, our algorithm has Õ(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.

Cite as

Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan, and Virginia Vassilevska Williams. Preprocessed 3SUM for Unknown Universes with Subquadratic Space. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 126:1-126:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kirkpatrick_et_al:LIPIcs.ICALP.2026.126,
  author =	{Kirkpatrick, Yael and Kuszmaul, John and Mathialagan, Surya and Vassilevska Williams, Virginia},
  title =	{{Preprocessed 3SUM for Unknown Universes with Subquadratic Space}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{126:1--126:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.126},
  URN =		{urn:nbn:de:0030-drops-265158},
  doi =		{10.4230/LIPIcs.ICALP.2026.126},
  annote =	{Keywords: Graph Algorithms, Diameter, Distance Oracle, Approximation Algorithm}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.94

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Authors: Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

The AP-LCA problem asks, given an n-node directed acyclic graph (DAG), to compute for every pair of vertices u and v in the DAG a lowest common ancestor (LCA) of u and v if one exists, i.e. a node that is an ancestor of both u and v but no proper descendent of it is their common ancestor. Recently [Grandoni et al. SODA'21] obtained the first sub-n^{2.5} time algorithm for AP-LCA running in O(n^{2.447}) time. Meanwhile, the only known conditional lower bound for AP-LCA is that the problem requires n^{ω-o(1)} time where ω is the matrix multiplication exponent. In this paper we study several interesting variants of AP-LCA, providing both algorithms and fine-grained lower bounds for them. The lower bounds we obtain are the first conditional lower bounds for LCA problems higher than n^{ω-o(1)}. Some of our results include: - In any DAG, we can detect all vertex pairs that have at most two LCAs and list all of their LCAs in O(n^ω) time. This algorithm extends a result of [Kowaluk and Lingas ESA'07] which showed an Õ(n^ω) time algorithm that detects all pairs with a unique LCA in a DAG and outputs their corresponding LCAs. - Listing 7 LCAs per vertex pair in DAGs requires n^{3-o(1)} time under the popular assumption that 3-uniform 5-hyperclique detection requires n^{5-o(1)} time. This is surprising since essentially cubic time is sufficient to list all LCAs (if ω = 2). - Counting the number of LCAs for every vertex pair in a DAG requires n^{3-o(1)} time under the Strong Exponential Time Hypothesis, and n^{ω(1,2,1)-o(1)} time under the 4-Clique hypothesis. This shows that the algorithm of [Echkardt, Mühling and Nowak ESA'07] for listing all LCAs for every pair of vertices is likely optimal. - Given a DAG and a vertex w_{u,v} for every vertex pair u,v, verifying whether all w_{u,v} are valid LCAs requires n^{2.5-o(1)} time assuming 3-uniform 4-hyperclique requires n^{4-o(1)} time. This defies the common intuition that verification is easier than computation since returning some LCA per vertex pair can be solved in O(n^{2.447}) time.

Cite as

Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 94:1-94:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mathialagan_et_al:LIPIcs.ICALP.2022.94,
  author =	{Mathialagan, Surya and Vassilevska Williams, Virginia and Xu, Yinzhan},
  title =	{{Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{94:1--94:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.94},
  URN =		{urn:nbn:de:0030-drops-164359},
  doi =		{10.4230/LIPIcs.ICALP.2022.94},
  annote =	{Keywords: All-Pairs Lowest Common Ancestor, Fine-Grained Complexity}
}

Search Results

Documents authored by Mathialagan, Surya

Preprocessed 3SUM for Unknown Universes with Subquadratic Space

Abstract

Cite as

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Abstract

Cite as

Thanks for your feedback!

Could not send message