Truly Subquadratic 3SUM and Subcubic APSP Break Decades-Old Barriers, Reportedly with Claude's Help
Josh Alman and Virginia Vassilevska Williams posted an arXiv preprint, "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs," delivering the first polynomial improvements for two textbook problems: deterministic O(n^1.9992) for 3SUM on n polynomially-bounded integers, and O(n^2.9995) for integer-weight APSP. These break the long-standing n² and n³ barriers, effectively refuting the 3SUM and APSP hypotheses and reshaping fine-grained complexity theory. Social media reports say Anthropic's Claude contributed to discovering the core algorithms, though no direct statement from the paper or Anthropic is available yet.
Confirmed
- The paper gives deterministic algorithms, the first truly subquadratic/subcubic results for 3SUM and APSP, for polynomially-bounded integer inputs with polynomial-related conditions
- The paper comes with a Lean formalization and claims to refute the randomized integer Word-RAM 3SUM conjecture—per @basedjensen, ranked 159th on the authors' own list of most important open math problems—and states Claude contributed to finding refutation algorithms for 3SUM, APSP, and ExaTime-related problems
- Per @thegautamkamath relaying Ilya Razenshteyn, Claude produced an O(n^1.9992) algorithm for 3SUM (deciding whether three of n integers sum to zero) with a Lean-formalized proof
- @AMBNNJ says an internal Anthropic model independently discovered algorithms breaking the quadratic/cubic barriers; @robleclerc adds that the internal model found the core algorithms while exploring open problems, which researchers then simplified into proven polynomial speedups for both problems
- Per @arannayebi, the same day saw multiple TCS breakthroughs: sub-n·log n FFT (new integer multiplication bound), subcubic APSP, subquadratic 3SUM, and a proof of the KLS conjecture; he joked the day shook his faith in human algorithmic ability
- Per @HankYeomans relaying Przemek Chojecki, Claude helped improve polynomial bounds for the 3SUM-Hard family, which some see as progress toward P=NP
- Per @arannayebi quoting NoahCitron's quip: mathematicians think math is beautiful, machines think it is not—humans simply happened to find the elegant solutions first, and the machine-derived subquadratic 3SUM algorithm is a case in point
Unconfirmed
- Claude's involvement is so far reported only via social media (@AMBNNJ, @thegautamkamath, @robleclerc, @basedjensen, etc.), without direct elaboration in the paper or from Anthropic
Why it matters
- The 3SUM and APSP hypotheses are pillars of fine-grained complexity, underpinning many conditional lower bounds; their refutation forces a redrawing of the field's landscape
- Comments relayed by @thegautamkamath call it a genuinely remarkable result that also takes much of the fun out of the field, as many classic hardness assumptions now wobble
- If Claude's involvement is confirmed, it would mark a landmark case of AI achieving a substantive breakthrough in open theoretical research, suggesting automated search may find algorithms humans long missed due to a preference for "elegant" solutions
2026-10-06 ~ 2026-10-08 · 13 related posts
- Episode 1: Truly Subquadratic 3SUM and Subcubic APSP Break Decades-Old Barriers, Reportedly with Claude's Help(2026-10-06, 13 posts)
- Episode 2: Integer Multiplication Breaks the n log n Barrier, with AI Leading the Way(2026-10-07, 11 posts)
- Episode 3: OpenAI's 'Below n log n' Claim Called Out as Wordplay(2026-10-07, 2 posts)
- Episode 4: AI Agents Chase Integer Multiplication Complexity Records in Viral Livestream(2026-10-08, 4 posts)
Primary sources
- Anthropic's internal model found the first truly subquadratic 3SUM algorithm, preprint claims — AMBNNJ ·
- Claude produces O(n^1.9992) 3SUM algorithm with Lean proof, vetted by top experts — thegautamkamath ·
- 3SUM Solved in O(n^1.9992): Alman & Vassilevska Williams Refute the 3SUM and APSP Hypotheses — auto_grad_ ·
- Truly subcubic APSP and truly subquadratic 3SUM breakthrough reshapes fine-grained complexity — thegautamkamath · 2026-10-06
- [source] Claude produces O(n^1.9992) 3SUM algorithm with Lean proof, vetted by top experts — thegautamkamath · 2026-10-06
- [source] 3SUM Solved in O(n^1.9992): Alman & Vassilevska Williams Refute the 3SUM and APSP Hypotheses — auto_grad_ · 2026-10-06
- [source] Anthropic's internal model found the first truly subquadratic 3SUM algorithm, preprint claims — AMBNNJ · 2026-10-06
- New arXiv paper refutes 3SUM and APSP hypotheses; Claude credited with subquadratic algorithm — burny_tech · 2026-10-06
- Paper with Lean formalization claims Claude-found algorithm disproves 3SUM conjecture — basedjensen · 2026-10-06
- AI-Discovered Algorithm Delivers First True Subquadratic 3SUM and Subcubic APSP — FrnkNlsn · 2026-10-06
- Anthropic Internal Model Reportedly Solves 3SUM and APSP Open Problems — robleclerc · 2026-10-07
- Anthropic claims 3SUM bounds breakthrough with Lean-verified Claude-assisted proof — HankYeomans · 2026-10-07
- Sub-n log n FFT, subcubic APSP and subquadratic 3SUM in one day stun algorithmists — burny_tech · 2026-10-07
- Machines don't care about elegance: an O(n^1.9992) algorithm for 3SUM — aran_nayebi · 2026-10-08
2 near-duplicate retellings: ctjlewis · aran_nayebi