Matrix multiplication is <=O(n^2.25) actually... [1]

1. https://github.com/openai/math/blob/main/preprints/Matrix-Mu...

Given that c is the speed of causality itself, FTL communications would effectively be like predicting the future.

From that angle, beating light speed by some absurdly tiny factor would probably correspond to a means of predicting the future at some almost absurdly tiny factor better than random guessing.

Edit: Actually...it doesn't make sense to call this FTL communication, it's just predicting the future state of a system given some previous state. FTL comms would have to be predicting the future state of a system without information about the previous state.

Practically speaking predictive modeling would be a means of compensating for light speed comms, kind of like branch prediction in processors or speculative decoding in LLMs, but that wouldn't actually be FTL comms.

If there was a way to do FTL communications you’d expect that Jane Street would have found it already

Are time and distance, and consequently velocity, even well defined enough at that level of precision on any physical scale?

That would only mean we calculated c wrong

What's FTL?

> IIRC, the GapCVP results were released with a 1/n^400 complexity term, but people quickly got it down to 1/n^8 by more careful accounting.

sqrt(n) now https://github.com/Mira-acc/cvp

You didn't believe!

This is better

The relative difference is so absurdly small to be irrelevant at any realisable input size. At least that's my read; e.g. even at n=10^80 (~number atoms in universe), the relative difference is ~0. That's still probably underselling how similar this is to n log n.

The -182 feels highly arbitrary.

It's potentially very interesting because there are a number of critical algorithms that are all related and share asymptotic lower bounds as a result. My first thought on seeing this was whether a proven result here would also open the door for FFTs to go below O(n log n).

It's like when Tony Hawk did a 900 for the first time. Now 900s in skateboarding aren't a big deal, kids can do it now. It was proving to the world what was possible was the mental hurdle that inspires others to actually try at the problem harder.

i understand this, but it always feels like we are being tricked when they say "integer multiplication below nlogn" because we intuit that that must mean "faster integer multiplication below nlogn EVERYWHERE!". but in reality it comes with 15 asterisks about the conditions that must be true for their statement to hold true.

Your issue is that I am viewing this proof as what it really is in terms of progressing the field and not from an imaginative perspective. I think that it is important to ground our selves somewhat in reality when discussing research like this because at the end of the day open ai is not doing for fun either.

openai wants to show the world what their product can do and i am simply not impressed

Incidentally, the previous most efficient known algorithm for integer multiplication was co-discovered by the chief author of GNU TeXmacs, a typesetting word processor.

It's 50 pages and cites this other paper in the same repo:

OpenAI. An explicit power saving for the exact discrete Fourier transform.

Here's a random excerpt:

8.3 The middle transform and the final permutation The factor QFt in (35) can be computed from a cyclic convolution and two pointwise phase multiplications. The chirp identity below performs the frequency change in Q without applying Q as a separate permutation of the array. The second identity shows how the retained source permutation R cancels when computing a convolution. Here ∗ denotes cyclic convolution on the product of the coordinate groups and a dot denotes coordinatewise multiplication.

Sure, all of this might end up being very unpleasant, and I'm glad not to be a mathematician right now. But that's still better than a future where there aren't even any questions left that we can understand and an AI can't solve.

Also, it still seems that AI has a much different style from humans, with more brute force and using obscure literature results, and the future might still end up human/AI complementary. We aren't in an AlphaZero situation where the AI learns everything through self-play. (Yet? But we don't even seem to be moving that way much? Can anybody qualified help out?) Things are just moving really fast now and it's hard to process everything.