Patrick

Here's an algorithm, developed by AI, that turns a whole bunch of problems that used to take n^k time, for k=2,3 into problems that take n^(k-smidgen), for various values of smidgen. Now presumably a lot of work will go into increasing the size of the smidgen. Some of these problems have stood for decades. It's a pretty major advance in polynomial complexity. It sounds like somebody at Anthropic ran across it while asking Claude to solve another problem, and handed the result over to the two outside researchers who wrote the paper, and paid them to investigate it. Which sure is a weird procedure. It's a conspicuously well-written, clear, and compendious paper. I haven't read the whole thing, but I read enough to get the basic good idea. It's a Strassen-type reduction in the exponent for speeding up the multiplication of tall skinny matrices, where you only care about a few elements of the output. Then you can use that in the inner loop of a bunch of algorithms, lowering their exponent. Unfortunately the constant factors are too big to be practical, but often that gets fixed later, and it becomes of interest to an engineer like me. arxiv.org/abs/2610.06783