r/singularity • u/AMBNNJ ▪️ • 1h ago
AI Internal Anthropic model refuted the 3SUM and APSP hypotheses: first truly subquadratic 3SUM and truly subcubic APSP (Alman & Vassilevska Williams)
https://arxiv.org/abs/2610.06783New preprint gives deterministic O(n^1.9992) 3SUM and O(n^2.9995) integer-weight APSP. These are the first polynomial improvements over the textbook n² and n³ bounds. The key is a new thin matrix product algorithm, which known reductions turn into speedups for Exact Triangle, Zero-Weight k-Clique, Tree Edit Distance, and more. SETH and Orthogonal Vectors are unaffected.
Notably, the paper says an Anthropic research model found the core algorithm on its own, and the main theorems are formalized in Lean.
•
u/Dangerous-Sport-2347 57m ago
So quickly had astra analyze this since i lack the proper mathematical background, this is somewhat less impactful than the recent solving of navier-stokes, but of similar order of magnitude in difficulty. Shows openAI has no insurmountable leads in mathematics and models are just reaching new capability thresholds in general.
Would be interesting to hear what internal model was used and how much budget it needed. Navier stokes they implied they used Bel and ~6 million $ in compute.
•
u/FateOfMuffins 53m ago
But OAI also does not know how much compute they actually needed to use for NS - Noam Brown says he wouldn't even attribute 10% of the result to the 10,000 agent swarm, he just thinks the underlying model was that good.
Anyways the paper here says
How the result was originally found and shared with the authors. 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.
But no idea about how much other stuff was tried or failure rate or etc
•
u/Dangerous-Sport-2347 43m ago
Had missed that part about token usage, if close to true and making some guesstimates on pricing that would be ~2000$ in token cost, which would be crazy low for being able to make true novel findings in important fields.
•
u/FateOfMuffins 42m ago
But we don't know the failure rates and other attempts.
The 10 problems OAI posted from Astra were what, $200?
Hard to compare costs on this without full disclosure from both labs
•
u/ineedanamegenerator 26m ago
Opus says the trick they found is genuinely novel but real-life impact is near zero in this case.
But now that we know this trick exists, other use-cases might be found/fine-tuned where the impact is real.
•
u/Zuzrich 1h ago
P = NP when?
•
u/sturdy-guacamole 53m ago
P=NP, if exist, will result in quite the boon for placement and routing
•
•
•
u/lhrad 55m ago
I haven't read the paper in all details, but at first glance it seems they apply some (new?) matrix multiplication algorithm which makes 3SUM theoretically faster, but this is like an implementation trick in a sense. It is not like "I figured out how 3SUM can be solved faster", it is like "if you implement existing 3SUM algos but use my matrix multiplication it is faster". Selling this matrix multiplication trick as improvement on such problems is quite misleading.
•
u/interfaceTexture3i25 AGI 2035 49m ago
That is how research mostly works these days. The low-hanging fruits have been figured for the most part, and anyway what difference would 1.9992 and 2.9995 make against 2 and 3 anyway?
•
•
u/anemotor 15m ago
All the difference in the world. Nobody cares about the practical speed-up.
•
u/interfaceTexture3i25 AGI 2035 6m ago
Yeah of course it makes a lot of difference in terms of ideas. I'm not talking about that, I'm talking about the practical speed-up
•
u/anemotor 2m ago
To give an idea, this paper demolishes an entire area of research, or nearly so. In its own way, it is far more impactful than Navier-Stokes.
•
u/lhrad 9m ago
I mean if I wrote this I would have positioned it as a theoretically improved matrix product with corollaries for 3SUMx etc. In this case, the authors intentionally go for a more sensational presentation that is misleading. You could still make it accepted at fine venues and you don't try to trick anyone.
In one sense, it is very much important that it is possible to go sub2 or sub3 for theoretical research and it motivates further research which one day might actually lead to better algos in practice. As for the practical applications of this result I personally don't think it matters, especially that the authors claim the constants inside O(.) are enormous. For example, 1000n1.992 gets below n2 at n=103750 or so, we are by far not at that scale.
•
•
•
u/Swimming_Gain_4989 21m ago edited 16m ago
Is this 3sum referring to the classic "given an array n and target k find 3 numbers in n that sum to k"?
•
u/chlebseby ASI 2030s 1h ago
those words and numbers probably means something important