Decades-Old 3SUM and APSP Complexity Barriers Finally Broken
Alman and Vassilevska Williams give the first polynomial-time improvements over textbook algorithms for 3SUM (O(n^1.9992)) and All-Pairs Shortest Paths (O(n^2.9995)), refuting the long-standing 3SUM, APSP, Exact Triangle, and related fine-grained complexity hypotheses. The results stem from a new algorithm for 'thin' matrix products, built on a Coppersmith/Schönhage-style identity, which computes only the matrix entries needed rather than the full product, and this is shown to solve a sparse triangle-detection problem that underlies all these hardness conjectures. Twitter reaction treated this as a major breakthrough in fine-grained complexity theory, with some tweets excitedly noting it beats a long-anticipated barrier (jokingly compared to the wait for GTA 6). A separate thread of confusion/skepticism arose from claims circulating that 'Claude discovered the algorithm,' which conflicts with the paper's actual human authorship (Alman and Vassilevska Williams) and prompted questions about how such AI-authorship claims should even be evaluated or cited.
Discussion: 7 tweets from 7 authors · @mahdi_tcs_, @evima0, @_Mira___Mira_, @Quasilocal, @nojobafterphoto +2