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.
Right now, I'm having LLMs audit the actual math in claimed arXiv solutions because despite its policy changes, arXiv is still a dumping ground. The audits have already found six faulty proofs that caused status issues for problems that should still clearly be fully open.
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?
The idea is that you can solve 3SUM by solving an instance of Triangles in Sparse Graphs, but 3SUM produces instances where those graphs are lopsided (i.e., tripartite graphs where one of the parts is much smaller than the other two). They found an efficient algorithm for those kinds of instances, and therefore an efficient algorithm for 3SUM.
Yeah, I found that tricky to parse too. But what they mean is that "Triangles in Sparse Lopsided Graphs" is the technique they used to exhibit "Truly Subquadratic 3SUM and Truly Subcubic APSP"
> 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.
The version in the acknowledgements is the one you want:
> An Anthropic employee used an internal research model to investigate open problems in the theory of cryptography. One of them was about cryptographic constructions based on the average-case hardness of Zero-k-Clique [LLV19, AHY25]. Claude was tasked with verifying and improving the constructions, but instead developed this algorithm, first for the average case, then for the worst case. The session used 16M output tokens with no human input.
> Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement, offered compensation, and provided access to the public version of Claude.
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.
It feels different to me from the CS side - this paper in particular feels likely to open up new research instead of closing it off, and I find that really exciting and a worthwhile use of AI. Showing that there's a (completely impractical but who's counting) algorithm better than the previously hypothesized lower bounds seems like the kind of thing that will inspire a scramble to keep beating it (and figure out the true lower bound). I give this one a thumbs up.
Yeah but at least IMO TCS has little to do with real world optimization. Real world optimization uses the easiest possible algorithms with very simple ideas like min-cut flows.
Absolutely! This is unlikely to directly, or even in the next 20 years, result in anything practical. But it has a very similar feel to Stotgers' and then Virginia Williams' earlier improvement on matrix multiply, where his thesis and her first paper was followed by a dozen others finding ways to build on it after years of seeing no progress on the problem at all. None of them have resulted in anything practical but who cares, really? Understanding the problem better is good and maybe some time in the next hundred years it'll result in an improvement in practice also. Or not. :)
> As a former mathematician, I'm kind of over them using the LLM for math.
As a non-mathematician who sometimes works on mathematical problems, I find this really puzzling. Why aren't mathematicians excited about the frontiers being unlocked by AI? The ability to discover more of the mathematical universe more readily?
> Why aren't mathematicians excited about the frontiers being unlocked by AI?
For the mathematicians who still are in academia: I guess because the competition for research positions (in particular permanent ones) is already insane; they probably feel that AI makes this kind of competition even worse.
I am not representative of all mathematicians and I definitely use LLMs to snag problems I couldn't in my previous life. But we now know that they are good at math.
I want lower energy bills, lower rent, better understanding of health etc. more than I want theorems.
> I want lower energy bills, lower rent, better understanding of health etc. more than I want theorems.
These efforts aren't mutually exclusive. I hate to be snide, but a lot of people would criticize you for being a mathematician because they want lower energy bills, lower rent, better understanding of health etc
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?
3sum hard was colloquially considered to be >= n^2
It's an absolutely unbelievable result! (Personally, this is more meaningful to me than Navier Stokes and feels more surprising - not that an agent did it but the result itself is extremely surprising!)
3SUM is (was?) one of the key conjectures in fine-grained complexity, mostly used to derive lower bounds for other problems. As such, most did not think a subquadratic algorithm was possible. Similar for APSP
> A galactic algorithm is an algorithm with record-breaking theoretical (asymptotic) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.
It's more that it demonstrates that it's possible at all. We now know that the floor isn't an exponent of 2, which makes pursuing further improvements way more valuable.
Yes because now it opens the door for future algorithms to chip away at that exponent where as in the past it may have seemed that an exponent of 2 was the floor.
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.
does that site have a list of solutions/dates they come out? or do you remove problems once they've been solved?
Yes, you can see the latest resolved ones here: https://www.proofatlas.ai/open-problems/#resolved-problems. I'm currently doing updates in batches, but I'm about to switch to daily updates.
Right now, I'm having LLMs audit the actual math in claimed arXiv solutions because despite its policy changes, arXiv is still a dumping ground. The audits have already found six faulty proofs that caused status issues for problems that should still clearly be fully open.
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?
The idea is that you can solve 3SUM by solving an instance of Triangles in Sparse Graphs, but 3SUM produces instances where those graphs are lopsided (i.e., tripartite graphs where one of the parts is much smaller than the other two). They found an efficient algorithm for those kinds of instances, and therefore an efficient algorithm for 3SUM.
Oh wow, that is truly awesome then! I thought it was a qualifier, but it actually is the means of solution (yeah, confusing title).
Yeah, I found that tricky to parse too. But what they mean is that "Triangles in Sparse Lopsided Graphs" is the technique they used to exhibit "Truly Subquadratic 3SUM and Truly Subcubic APSP"
> 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.
The version in the acknowledgements is the one you want:
> An Anthropic employee used an internal research model to investigate open problems in the theory of cryptography. One of them was about cryptographic constructions based on the average-case hardness of Zero-k-Clique [LLV19, AHY25]. Claude was tasked with verifying and improving the constructions, but instead developed this algorithm, first for the average case, then for the worst case. The session used 16M output tokens with no human input.
> Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement, offered compensation, and provided access to the public version of Claude.
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.
It feels different to me from the CS side - this paper in particular feels likely to open up new research instead of closing it off, and I find that really exciting and a worthwhile use of AI. Showing that there's a (completely impractical but who's counting) algorithm better than the previously hypothesized lower bounds seems like the kind of thing that will inspire a scramble to keep beating it (and figure out the true lower bound). I give this one a thumbs up.
Yeah but at least IMO TCS has little to do with real world optimization. Real world optimization uses the easiest possible algorithms with very simple ideas like min-cut flows.
Absolutely! This is unlikely to directly, or even in the next 20 years, result in anything practical. But it has a very similar feel to Stotgers' and then Virginia Williams' earlier improvement on matrix multiply, where his thesis and her first paper was followed by a dozen others finding ways to build on it after years of seeing no progress on the problem at all. None of them have resulted in anything practical but who cares, really? Understanding the problem better is good and maybe some time in the next hundred years it'll result in an improvement in practice also. Or not. :)
> As a former mathematician, I'm kind of over them using the LLM for math.
As a non-mathematician who sometimes works on mathematical problems, I find this really puzzling. Why aren't mathematicians excited about the frontiers being unlocked by AI? The ability to discover more of the mathematical universe more readily?
> Why aren't mathematicians excited about the frontiers being unlocked by AI?
For the mathematicians who still are in academia: I guess because the competition for research positions (in particular permanent ones) is already insane; they probably feel that AI makes this kind of competition even worse.
I am not representative of all mathematicians and I definitely use LLMs to snag problems I couldn't in my previous life. But we now know that they are good at math.
I want lower energy bills, lower rent, better understanding of health etc. more than I want theorems.
> I want lower energy bills, lower rent, better understanding of health etc. more than I want theorems.
These efforts aren't mutually exclusive. I hate to be snide, but a lot of people would criticize you for being a mathematician because they want lower energy bills, lower rent, better understanding of health etc
The interesting thing isn't that we now know they can do math. The interesting is that these problems now can be trivially solved.
The value of LLM is not "Ha curious look what it can do". It's not entertainment.
Because the whole field relies on reputation, and there is a view that using AI to help your research is not good for your reputation.
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?
Nobody thought this was possible.
3sum hard was colloquially considered to be >= n^2
It's an absolutely unbelievable result! (Personally, this is more meaningful to me than Navier Stokes and feels more surprising - not that an agent did it but the result itself is extremely surprising!)
3SUM is (was?) one of the key conjectures in fine-grained complexity, mostly used to derive lower bounds for other problems. As such, most did not think a subquadratic algorithm was possible. Similar for APSP
But from what I understand this doesn't refute SETH, no?
> But from what I understand this doesn't refute SETH, no?
SETH: Strong Exponential Time Hypothesis
See https://en.wikipedia.org/w/index.php?title=Exponential_time_...
No it does not.
Is n to the 1.9992 practically speaking subquadratic? Technically, yes, but is there a practically useful result here?
> A galactic algorithm is an algorithm with record-breaking theoretical (asymptotic) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.
https://en.wikipedia.org/wiki/Galactic_algorithm
It's more that it demonstrates that it's possible at all. We now know that the floor isn't an exponent of 2, which makes pursuing further improvements way more valuable.
Yes because now it opens the door for future algorithms to chip away at that exponent where as in the past it may have seemed that an exponent of 2 was the floor.
Some more comments earlier: https://news.ycombinator.com/item?id=49973854
Holy crap, this is huge if it is correct.