Rendered at 23:47:47 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
zone411 1 days ago [-]
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.
ItsMattyG 1 days ago [-]
does that site have a list of solutions/dates they come out? or do you remove problems once they've been solved?
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.
djoldman 1 days ago [-]
> 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.
dcre 1 days ago [-]
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.
vatsachak 1 days ago [-]
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.
dgacmu 1 days ago [-]
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.
jltsiren 1 days ago [-]
This paper was more about closing off research, but in an amusing way.
There are a lot of results about conditional lower bounds: "If this problem is at least this hard, that other problem must be at least that hard." But now a widely used assumption was proven wrong, and an entire house of cards collapsed.
It feels like that particular research direction is now a dead end, until we can figure out a way of proving conditional bounds that is robust against technicalities. We would like to prove something like "If this problem is essentially at least this hard, that other problem must be essentially at least that hard." If the conditional bound depends on the assumption that the first problem requires at least n^2 time but somebody comes up with an O(n^1.9992) time algorithm, a slightly weaker conditional bound would still remain.
akoboldfrying 23 hours ago [-]
> It feels like that particular research direction is now a dead end
This is the most negative possible take on the most positive possible kind of result in CS.
To see just how unduly negative it is, imagine how different your response would have been had the exact same result been reported in a paper by exclusively human authors. Would you have likewise accused them of creating a research "dead end"?
EDIT: Changed "by, e.g., Ryan Williams" to "by exclusively human authors". Without having checked the authors, who include Ryan's wife and frequent collaborator Virginia, I had reached for a big name in the field purely as an example of a human who might well have made this breakthrough on their own.
dgacmu 23 hours ago [-]
Yeah, I can't get behind this. By showing one problem had an improved lower bound, they showed that another five algorithms could also be improved, and, yes, they refuted the 3SUM hypothesis and made a lot of conjectures about the hardness of some problems less certain, but now ... now we have to go figure those out more precisely. Which is great. It's progress! And all of the work put into those reductions was what made this one result topple five algorithms, so it's not like it's been wasted work.
jltsiren 23 hours ago [-]
There is a difference between one-off results and processes that can generate new results at an industrial scale.
Conditional lower bounds are a way of building understanding of the essential difficulty of specific computational problems. But if AI can now routinely generate marginal improvements, conditional bounds based on unproven assumptions become a waste of effort.
This is mostly due to how mathematics works. Ideally, we would like to prove something like "if problem A is essentially this difficult, problem B is essentially that difficult". But what we actually prove is more like "if (specific formulation of the difficulty of problem A), then (specific formulation of the difficulty of problem B)".
But those specific formulations become fixed targets for the AI to attack. If it manages to break the specific assumption, for example by creating an O(n^1.9998) time algorithm that is for all intents and purposes worse than a naive O(n^2) time algorithm, the conditional result becomes void. We could try to salvage the result with a different formulation, but that again becomes a fixed target.
This is essentially Goodhart's Law. We measure improvement with highly precise metrics, while we are actually interested in qualitative understanding.
EDIT: If theorems and proofs become cheap, marginal improvements are no longer interesting. Qualitatively better algorithms or unconditional lower bounds would be actual contributions. As would be a specific formulation of a conditional result that is robust against technical improvements made by AI targeting that specific formulation.
akoboldfrying 19 hours ago [-]
> There is a difference between one-off results and processes that can generate new results at an industrial scale.
This is the part of your reply that I find the most compelling. If such results can be produced "cheaply", then yes, it becomes less interesting for humans to devote their own time and energy to pursuing them. But while that would be bad news for mathematicians, I don't hold that to be a negative thing on its face. (I'm not sure that you do either, but it's a commonly held view and consistent with your words so far.) Fundamentally, that's because I don't think mathematicians have a right to do mathematics research for a living any more than buggy whip manufacturers have a right to make buggy whips for a living.
On the (to my mind, secondary) question of whether "small"/"technical" advances in algorithms will now become cheap: I don't think this will happen in any case. Unlike most applications of Goodhart's Law, which involve exploiting something trivial like line counts or git commits, I think improving a well-known problem's asymptotic complexity is sufficiently "meaty" that it will never be cheaply automated. Even if some theorem is discovered in future that "automates" optimal algorithm creation for a wide range of problems (imagine something like a turbocharged Courcelle's Theorem), I'm certain there will always be problems for which we don't know the answer.
itemize123 22 hours ago [-]
it just means that the assumptions we are making in the first place is wrong?
nothing here is a dead-end because essentially we are at the same place before.
people might even go ahead and say now if it's n^1.5 what happens, what results can be true.
i feel like you are arguing there is -- even in the narrow utility of PROOFS -- there is a goodness in being an ostrich with its head in the sand. If that's true, people can still be that ostrich and pretend the bound is now n^1.9 or something.
jltsiren 22 hours ago [-]
I edited my comment just as you answered, but I'll also say it here in a different way.
The actual conditional result was "if problem A is essentially this difficult, problem B is essentially that difficult". A specific formulation of it was proven, but it depended on a specific assumption that was just shown false. But the general result is still probably valid, because the general assumption holds. But there may be no point in going through the effort of proving another specific formulation, when the automatic theorem factory could just come up with another technical improvement targeting that formulation.
I started in theoretical computer science, but I quickly drifted to more applied areas, because I was annoyed with how often theoreticians would confuse the map for the territory. But if AI can now do that much more efficiently than any human, perhaps theoreticians will have to rethink how much they should focus on specific provable statements.
vatsachak 1 days ago [-]
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.
dgacmu 1 days ago [-]
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 Stothers' and then Virginia Williams' earlier improvement on matrix multiply, where his thesis and her first paper were followed by a dozen others finding ways to build on it after 20 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. :)
vatsachak 1 days ago [-]
Nice. That's why I'm a former mathematician haha
jey 1 days ago [-]
> 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?
aleph_minus_one 1 days ago [-]
> 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.
vatsachak 1 days ago [-]
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.
PhunkyPhil 1 days ago [-]
> 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
TripolitianFish 8 hours ago [-]
I don’t think you hate to be snide even a little bit, if I’m honest. The difference being that the entirety of mathematics research has never pulled in the CapEx that anthropic or OAI is. Mathematicians in academia are mostly paid to teach, mind you.
I’m personally pretty excited by the results coming from these labs, but trying to dismiss the capital allocation objection with “but what about” is really silly.
PhunkyPhil 7 hours ago [-]
You can't just look at the funding for math departments. I think the value generation potential of every mathematician in the world could exceed that of the capex of these companies. How much is "lost" when a brilliant mind goes into pure math research instead of nuclear engineering, or civil engineering etc. Cumulatively, a lot.
Edit: I'm fine saying we're spending too much money on AI, in fact I agree, but "theorems" are not the only output of these companies. It's almost definitely not going to be worth the expenditure, but the benefits are not going to be only lean proofs
aleph_minus_one 60 minutes ago [-]
> I think the value generation potential of every mathematician in the world could exceed that of the capex of these companies. How much is "lost" when a brilliant mind goes into pure math research instead of nuclear engineering, or civil engineering etc. Cumulatively, a lot.
This is already the situation that we have: because of the fierce competition for temporary academic positions, and very little hope for permanent positions, large quantities of really good mathematicians leave academia and work in a job that has basically nothing with mathematics (many mathematicians consider these jobs as bullshit jobs, but they pay the bill).
itemize123 22 hours ago [-]
obviously the overlap is tiny so people are not excited.
And yes, nobody is that excited about vatsachak's mathematician-ism. it's just a thing he do. And now it's just a thing AI do.
rowanG077 1 days ago [-]
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.
trostaft 1 days ago [-]
> Why aren't mathematicians excited about the frontiers being unlocked by AI?
Well, I wouldn't generalize based off of the thread OP (and people on social media, including me). I think a lot of us are very excited! Most of my collaborators are, including myself.
There's a lot of simultaneous social change that's accompanying these tools, not all of which is positive. Agonized screaming is pretty loud, relatively speaking to the rest of the conversation.
warkdarrior 1 days ago [-]
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.
kevinwang 1 days ago [-]
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?
wrsh07 1 days ago [-]
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!)
SyzygyRhythm 1 days ago [-]
Do you have any more detail on this? When I first saw the 3SUM result, it was accompanied with a comment something like "There is the obvious O(n^3) algorithm, and a pretty easy O(n^2) algorithm". I thought for about 15 seconds and came up with: put all the numbers in a hash table (O(n)). Search every pair of numbers (O(n^2)) and check if the negative value is in the table (O(1)). I checked Wikipedia and that is basically the simple version (though there are algorithms with a lower constant and lower storage).
But it seems strange that an algorithm that I can come up with in 15 seconds (and I'm not very good at this) is also optimal! It's more surprising that this can't be beat (or couldn't be beat). So there must be something more to the story.
remywang 23 hours ago [-]
Yes that’s the idea, these conjectures basically say “there’s no better algorithm than the naive/brute force one”. It’s like if P!=NP, then there’s no (asymptotically) better algorithm for SAT than naive backtracking search.
akoboldfrying 23 hours ago [-]
I don't really understand. The fact that, until now, no one's been able to come up with a better algorithm than the one everyone thinks of in 15s is what makes it an interesting conjecture.
It's made more tantalising by the fact that O(n^2) is so much larger than O(n) (the obvious lower bound needed to read the input), which suggests "room" for "something clever to do better".
SyzygyRhythm 21 hours ago [-]
It's the "Nobody thought this was possible" that I found curious. Yes, there is a lot of room between O(n) and O(n^2)! That's why it seems strange that it would be thought impossible.
But I guess it is just that people have been working on it for a long time with no progress, and so the thought was that there must be something especially hard about it. And, well, there is something comforting about round numbers, and so O(n^2) is something special, whereas if the O(n^1.9992) algorithm was known from the start I doubt anybody would have been surprised if O(n^1.9991) was possible.
remywang 1 days ago [-]
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
sigbottle 1 days ago [-]
But from what I understand this doesn't refute SETH, no?
aleph_minus_one 1 days ago [-]
>
But from what I understand this doesn't refute SETH, no?
Is n to the 1.9992 practically speaking subquadratic? Technically, yes, but is there a practically useful result here?
itishappy 1 days ago [-]
> 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.
blovescoffee 1 days ago [-]
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.
stephen_cagle 1 days ago [-]
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?
gregdeon 1 days ago [-]
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.
stephen_cagle 1 days ago [-]
Oh wow, that is truly awesome then! I thought it was a qualifier, but it actually is the means of solution (yeah, confusing title).
jey 1 days ago [-]
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"
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.
> Claude also verified this paper’s main results using the Lean 4 proof assistant with the Mathlib library.
> 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.
There are a lot of results about conditional lower bounds: "If this problem is at least this hard, that other problem must be at least that hard." But now a widely used assumption was proven wrong, and an entire house of cards collapsed.
It feels like that particular research direction is now a dead end, until we can figure out a way of proving conditional bounds that is robust against technicalities. We would like to prove something like "If this problem is essentially at least this hard, that other problem must be essentially at least that hard." If the conditional bound depends on the assumption that the first problem requires at least n^2 time but somebody comes up with an O(n^1.9992) time algorithm, a slightly weaker conditional bound would still remain.
This is the most negative possible take on the most positive possible kind of result in CS.
To see just how unduly negative it is, imagine how different your response would have been had the exact same result been reported in a paper by exclusively human authors. Would you have likewise accused them of creating a research "dead end"?
EDIT: Changed "by, e.g., Ryan Williams" to "by exclusively human authors". Without having checked the authors, who include Ryan's wife and frequent collaborator Virginia, I had reached for a big name in the field purely as an example of a human who might well have made this breakthrough on their own.
Conditional lower bounds are a way of building understanding of the essential difficulty of specific computational problems. But if AI can now routinely generate marginal improvements, conditional bounds based on unproven assumptions become a waste of effort.
This is mostly due to how mathematics works. Ideally, we would like to prove something like "if problem A is essentially this difficult, problem B is essentially that difficult". But what we actually prove is more like "if (specific formulation of the difficulty of problem A), then (specific formulation of the difficulty of problem B)".
But those specific formulations become fixed targets for the AI to attack. If it manages to break the specific assumption, for example by creating an O(n^1.9998) time algorithm that is for all intents and purposes worse than a naive O(n^2) time algorithm, the conditional result becomes void. We could try to salvage the result with a different formulation, but that again becomes a fixed target.
This is essentially Goodhart's Law. We measure improvement with highly precise metrics, while we are actually interested in qualitative understanding.
EDIT: If theorems and proofs become cheap, marginal improvements are no longer interesting. Qualitatively better algorithms or unconditional lower bounds would be actual contributions. As would be a specific formulation of a conditional result that is robust against technical improvements made by AI targeting that specific formulation.
This is the part of your reply that I find the most compelling. If such results can be produced "cheaply", then yes, it becomes less interesting for humans to devote their own time and energy to pursuing them. But while that would be bad news for mathematicians, I don't hold that to be a negative thing on its face. (I'm not sure that you do either, but it's a commonly held view and consistent with your words so far.) Fundamentally, that's because I don't think mathematicians have a right to do mathematics research for a living any more than buggy whip manufacturers have a right to make buggy whips for a living.
On the (to my mind, secondary) question of whether "small"/"technical" advances in algorithms will now become cheap: I don't think this will happen in any case. Unlike most applications of Goodhart's Law, which involve exploiting something trivial like line counts or git commits, I think improving a well-known problem's asymptotic complexity is sufficiently "meaty" that it will never be cheaply automated. Even if some theorem is discovered in future that "automates" optimal algorithm creation for a wide range of problems (imagine something like a turbocharged Courcelle's Theorem), I'm certain there will always be problems for which we don't know the answer.
i feel like you are arguing there is -- even in the narrow utility of PROOFS -- there is a goodness in being an ostrich with its head in the sand. If that's true, people can still be that ostrich and pretend the bound is now n^1.9 or something.
The actual conditional result was "if problem A is essentially this difficult, problem B is essentially that difficult". A specific formulation of it was proven, but it depended on a specific assumption that was just shown false. But the general result is still probably valid, because the general assumption holds. But there may be no point in going through the effort of proving another specific formulation, when the automatic theorem factory could just come up with another technical improvement targeting that formulation.
I started in theoretical computer science, but I quickly drifted to more applied areas, because I was annoyed with how often theoreticians would confuse the map for the territory. But if AI can now do that much more efficiently than any human, perhaps theoreticians will have to rethink how much they should focus on specific provable statements.
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?
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 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
I’m personally pretty excited by the results coming from these labs, but trying to dismiss the capital allocation objection with “but what about” is really silly.
Edit: I'm fine saying we're spending too much money on AI, in fact I agree, but "theorems" are not the only output of these companies. It's almost definitely not going to be worth the expenditure, but the benefits are not going to be only lean proofs
This is already the situation that we have: because of the fierce competition for temporary academic positions, and very little hope for permanent positions, large quantities of really good mathematicians leave academia and work in a job that has basically nothing with mathematics (many mathematicians consider these jobs as bullshit jobs, but they pay the bill).
And yes, nobody is that excited about vatsachak's mathematician-ism. it's just a thing he do. And now it's just a thing AI do.
The value of LLM is not "Ha curious look what it can do". It's not entertainment.
Well, I wouldn't generalize based off of the thread OP (and people on social media, including me). I think a lot of us are very excited! Most of my collaborators are, including myself.
There's a lot of simultaneous social change that's accompanying these tools, not all of which is positive. Agonized screaming is pretty loud, relatively speaking to the rest of the conversation.
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!)
But it seems strange that an algorithm that I can come up with in 15 seconds (and I'm not very good at this) is also optimal! It's more surprising that this can't be beat (or couldn't be beat). So there must be something more to the story.
It's made more tantalising by the fact that O(n^2) is so much larger than O(n) (the obvious lower bound needed to read the input), which suggests "room" for "something clever to do better".
But I guess it is just that people have been working on it for a long time with no progress, and so the thought was that there must be something especially hard about it. And, well, there is something comforting about round numbers, and so O(n^2) is something special, whereas if the O(n^1.9992) algorithm was known from the start I doubt anybody would have been surprised if O(n^1.9991) was possible.
SETH: Strong Exponential Time Hypothesis
See https://en.wikipedia.org/w/index.php?title=Exponential_time_...
https://en.wikipedia.org/wiki/Galactic_algorithm