Truly subquadratic algorithms for 3SUM-hard problems

Given $n$ numbers, do three of them sum to zero? For decades this 3SUM problem was believed to need about $n^2$ time, and dozens of geometric problems were shown to be at least as hard. A 2026 preprint gives a truly subquadratic algorithm for 3SUM itself, but the reductions run only one way, so whether those geometric problems, such as finding three collinear points, can be solved in time $O(n^{2-\varepsilon})$ is now wide open.

Problem

3SUM. Given sets $A$, $B$, $C$ of numbers with $|A|+|B|+|C|=n$, decide whether there are $a\in A$, $b\in B$, $c\in C$ with $a+b=c$. After sorting, a linear scan for each $a\in A$ solves this in $O(n^2)$ time.

A problem is 3SUM-hard if 3SUM can be reduced to it with $o(n^2)$ overhead, so that a subquadratic algorithm for it would give one for 3SUM. Examples from computational geometry include deciding whether $n$ points in the plane contain three on a line (3-collinearity), and hence finding a minimum-area triangle, as well as some point-covering, motion-planning and polygon-containment problems [1], [5].

Question. Can 3SUM-hard problems be solved in truly subquadratic time, $O(n^{2-\varepsilon})$ for some constant $\varepsilon>0$? The central test case is 3-collinearity, for points with integer coordinates of polynomial size or for real points on the real RAM, possibly with randomization.

Background

Gajentaan and Overmars (1995) introduced 3SUM-hardness to explain why many geometric problems seemed stuck at quadratic time [1]; this is Problem 11 of The Open Problems Project. The conjecture that 3SUM needs $n^{2-o(1)}$ time was later used to derive lower bounds for dynamic data structures, triangle listing and string problems (Kopelowitz, Pettie and Porat, 2016). In October 2026 Alman and Vassilevska Williams refuted that conjecture [5]. Their algorithm speeds up 3SUM and problems that reduce to it, but not the geometric problems, which are only known to be at least as hard as 3SUM.

What is known

• 3SUM itself. Alman and Vassilevska Williams solve 3SUM on $n$ integers of polynomial size deterministically in $O(n^{1.9992})$ time, and on real numbers by a Las Vegas algorithm in $O(n^{1.998})$ expected time using only comparisons, additions and subtractions [5]. The integer result, with every lemma it relies on, has been formalized in Lean 4 with Mathlib on an explicit word-RAM model; the real-number result has not. Majdoddin improved the integer exponent to $1.9945+o(1)$ [6]. Both are unrefereed preprints from October 2026.
• Geometric problems. The authors of [5] note that whether three collinear points can be found in truly subquadratic time is now open, since the known reductions go from 3SUM to these problems and not back.
• Logarithmic speed-ups. Before 2026, the fastest 3SUM algorithms saved only logarithmic factors (Grønlund and Pettie, 2014; Chan, 2018 [4]), and Chan's methods also give logarithmic-factor speed-ups for some geometric 3SUM-hard problems [4].
• Decision trees. In linear decision trees whose queries involve only three input numbers, 3SUM needs $\Omega(n^2)$ queries (Erickson, 1999) [2], while general linear decision trees solve it with $O(n\log^2 n)$ queries (Kane, Lovett and Moran, 2019) [3].

What would count as progress

• A truly subquadratic algorithm for 3-collinearity, or for another 3SUM-hard geometric problem from [1], with a proof of its running time.
• A proof that 3-collinearity needs $n^{2-o(1)}$ time under a hypothesis that the 2026 algorithm leaves standing; the authors of [5] list Orthogonal Vectors and CNF-SAT among the problems it does not speed up.
• An independent check of [5], or a formal proof of its real-number result.

References

1. A. Gajentaan and M. H. Overmars, On a class of $O(n^2)$ problems in computational geometry, Comput. Geom. 5 (1995), 165–185. doi:10.1016/0925-7721(95)00022-2
2. J. Erickson, Lower bounds for linear satisfiability problems, Chicago J. Theoret. Comput. Sci. 1999(8). cjtcs.cs.uchicago.edu
3. D. M. Kane, S. Lovett and S. Moran, Near-optimal linear decision trees for $k$-SUM and related problems, J. ACM 66 (2019); STOC 2018. doi:10.1145/3285953, arXiv:1705.01720
4. T. M. Chan, More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems, Proc. SODA 2018, 881–897. doi:10.1137/1.9781611975031.57
5. J. Alman and V. Vassilevska Williams, Truly subquadratic 3SUM and truly subcubic APSP via triangles in sparse lopsided graphs, preprint (2026). arXiv:2610.06783
6. R. Majdoddin, Thin matrix products up to $D\le N^{0.172}$ and lossless reductions for 3SUM, Exact Triangle and APSP, preprint (2026). arXiv:2610.17420

Source

Imported from The Open Problems Project, Problem 11, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.