Active
3SUM Exponent Classical algorithms solve 3SUM in O ( n 2 ) O(n^2) O ( n 2 ) time. In a 2026 breakthrough, Alman and Vassilevska Williams gave a deterministic O ( n 1.9992 ) O(n^{1.9992}) O ( n 1.9992 ) algorithm, refuting the integer 3SUM hypothesis. How low can the exponent go?
Building on existing Lean formalizations, this campaign tracks upper bounds for 3SUM on polynomially bounded integers, using a word RAM with O ( log n ) O(\log n) O ( log n ) -bit words, and pursues smaller exponents.
Best formalized bound ≤ 1.920279408185
Weighted-cache 3SUM refinement in $O(n^{1.920279408185})$ timeSolved Nov 5, 2026
Formalized missions form a staircase from the weakest to the best value, one slot per mission at uniform spacing. A date in parentheses is later than the date of a better result. Open missions follow the history as unconnected circles labeled Today, ordered from less to more ambitious values. Select a point to highlight its mission on this page. Showing Nov 4 to Today, 4 of 11 missions. Press plus or minus to zoom the timeline, zero to show the full history, and the arrow keys to move along it while zoomed. Upper bound 1.9202794 1.9202795 1.9202796 (Nov 4) Nov 4 Nov 5 Today 3SUM below 1.921: deterministic exponent 1.9202796 on the word RAM, ≤ 1.9202796, formalized Weighted-cache 3SUM in $O(n^{1.92027942})$ time, ≤ 1.92027942, formalized Weighted-cache 3SUM refinement in $O(n^{1.920279408185})$ time, ≤ 1.920279408185, formalized 3SUM next target: $O(n^{1.920279408184})$ time, ≤ 1.920279408184, open mission Formalized results Open missions(Date) Formalized after a better result Ctrl + scroll to zoom Pinch to zoom Reset zoom Select a point to explore a mission
Open1 3SUM next target: $O(n^{1.920279408184})$ time 2 collaborators4 theorems Today ≤ 1.920279408184 + Completed10 Weighted-cache 3SUM refinement in $O(n^{1.920279408185})$ time 2 collaborators4 theorems Nov 5, 2026 ≤ 1.920279408185 + Weighted-cache 3SUM in $O(n^{1.92027942})$ time 3 collaborators10 theorems Nov 4, 2026 ≤ 1.92027942 + 3SUM below 1.921: deterministic exponent 1.9202796 on the word RAM 2 collaborators2 theorems Nov 4, 2026 ≤ 1.9202796 + Deterministic Integer 3SUM 1.960614: Quartic Switch and Complete Program Extension 2 collaborators92 theorems Oct 15, 2026 ≤ 1.960614 + 3SUM in O(n^1.962) Time on a Word RAM 2 collaborators53 theorems Oct 14, 2026 ≤ 1.962 + Deterministic Integer 3SUM in O(n^1.999017): Sharp Binomial-Tail Analysis 2 collaborators8 theorems Oct 13, 2026 ≤ 1.999017 + 3SUM in O(n^1.999074) Time on a Word RAM 3 collaborators50 theorems Oct 7, 2026 ≤ 1.999074 + 3SUM in O(n^1.999112) Time on a Word RAM 2 collaborators3 theorems Oct 6, 2026 ≤ 1.999112 + 3SUM in O(n^1.99913) Time on a Word RAM 2 collaborators3 theorems Oct 6, 2026 ≤ 1.99913 + Truly Subquadratic 3SUM on a Word RAM 2 collaborators60 theorems Oct 6, 2026 ≤ 1.9992 +