Internal Anthropic model refuted the 3SUM and APSP hypotheses: first truly subquadratic 3SUM and truly subcubic APSP (Alman & Vassilevska Williams)

[u/AMBNNJ]

https://arxiv.org/abs/2610.06783

New 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/lhrad]

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 → u/lhrad]

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/play_hard_outside → u/interfaceTexture3i25]

I suppose it depends on the problem size!

[u/anemotor → u/interfaceTexture3i25]

All the difference in the world. Nobody cares about the practical speed-up.

[u/interfaceTexture3i25 → u/anemotor]

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 → u/interfaceTexture3i25]

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 → u/interfaceTexture3i25]

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, 1000n^1.992 gets below n² at n=10³⁷⁵⁰ or so, we are by far not at that scale.

[u/anemotor → u/lhrad]

Fine-grained complexity doesn't actually care about practical algorithms. These conjectures served as "hardness pillar", and were used to establish the theoretical lower bound for a vast number of (practical) problems.