Yet another Hacker News

33 points mauriziocalo 5 hours ago 13 comments

djoldman 2 hours ago | parent

> 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 2 hours ago | parent

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.

kevinwang 1 hour ago | parent

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 25 minutes ago | parent

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!)

remywang 16 minutes ago | parent

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

these 1 hour ago | parent

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

itishappy 1 hour ago | parent

> 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

blovescoffee 1 hour ago | parent

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.

vatsachak 1 hour ago | parent

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.

jey 11 minutes ago | parent

> 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?

vatsachak 9 minutes ago | parent

I am not representative of all mathematicians and I definitely use LLMs to snag problems I couldn't in my previous life. But we are 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.

warkdarrior 7 minutes ago | parent

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.

ChrisArchitect 39 minutes ago | parent

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