Subquadratic 3SUM and Subcubic APSP

djoldman

> Claude, an AI model developed by Anthropic, discovered the algorithm that refutes the 3SUM, APSP, and Exact Triangle hypotheses. The authors then worked to understand, simplify, strengthen, and extend the algorithm, derive additional consequences, and make the presentation accessible. See “Acknowledgments and Methodology” for how the result was found and shared with the authors. The authors take full responsibility for this paper. > Claude also verified this paper’s main results using the Lean 4 proof assistant with the Mathlib library.

kevinwang

Wow, can anyone give the TCS community context on this? Would most people have thought these to be possible, to be impossible, or would most people not have thought about this before?

these

Is n to the 1.9992 practically speaking subquadratic? Technically, yes, but is there a practically useful result here?

vatsachak

As a former mathematician, I'm kind of over them using the LLM for math. we know it works. I want them pointed at "data construction", like being libraries, theories and experiments. But I guess they are deduction machines and there is a lot of low hanging fruit with superhuman deduction in math.

ChrisArchitect

Some more comments earlier: https://news.ycombinator.com/item?id=49973854

nialv7

Holy crap, this is huge if it is correct.

zone411

I maintain an LLM-ranked list of the 500 most important open problems in math at https://www.proofatlas.ai/open-problems/ . This problem was ranked #159, and it also resolved #244, "All-Pairs Shortest Paths in Truly Subcubic Time." It is formalized in Lean. But what's crazy is that within the last day or so, we've also gotten LLM-assisted solutions to #95, the Kannan–Lovász–Simonovits (KLS) conjecture, by three different authors in parallel (all extending Song–Zhang's key criterion introduced on Oct. 1), #278, the Mumford–Shah conjecture, and #227, Zauner's conjecture on SIC-POVM existence in every dimension, which also represents a major claimed advance on Hilbert's twelfth problem (#36) for real quadratic fields. This is likely because OpenAI's solutions to 100 open conjectures are expected to drop any day, so everyone is in a hurry not to get scooped.

stephen_cagle

The full title is "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs". Is that the same thing as getting subqudratic time in general 3SUM? How much carrying is the Sparse Lopsided Graph doing here?