The 3SUM hypothesis has, for more than a decade, functioned as a working law of fine-grained complexity. The claim was not merely that the textbook O(n²) algorithm is hard to improve, but that no O(n²⁻ᵋ) algorithm exists for any fixed ε>0. A large conditional lower-bound program was built on that premise.

Alman and Vassilevska Williams now give a deterministic O(n¹·⁹⁹⁹²) algorithm for n integers of polynomial size, and an O(n²·⁹⁹⁹⁵) algorithm for APSP. The savings are negligible in practice. They are decisive in theory: truly subquadratic 3SUM and truly subcubic APSP refute the hypotheses, and the reductions that once propagated hardness now propagate the speedup.

The core algorithm was not found by a direct attack on 3SUM. Asked to check cryptographic constructions based on the average-case hardness of Zero-k-Clique, an internal Claude model produced it instead, first in the average case and then in the worst case, with no human input in that session.

🄳🄾🄾🄼🄿🤖🅂🅃🄸🄽🄶