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.
> 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.
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.
> 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.
Wow, does anyone know give 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?
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.
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
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.
> 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.
Wow, does anyone know give 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?