Replace the complex numbers with a finite field and O(1) arithmetic stops being an unrealistic assumption, as you can actually perform the required operations in constant time on a real computer. You can't do that for infinitely-precise complex numbers, but you'll never be able to provide an infinitely-precise complex number as the input anyway. If you start with finite-precision numbers (e.g. 64-bit floats) you can do all operations in a finite-field representation (e.g. the Ozaki scheme II is an actually practical implementation of that idea for matrix multiplication https://arxiv.org/abs/2504.08009 ) and the magnitude of intermediate values is no longer a problem.

This reminds me of 'O(1)' hash maps, but far more egregious.

actually thinking about it more I think my oracle model is more powerful than the computer used in openai's fft but maybe its a good way to think about it.

The history of the term is actually really interesting. There has been debate about whether or not its the correct name basically since the advent of computer science departments in the 60s.

I don't think the author is "wrong" about the gap between theoretical discussions computation and the actual design constraints of building usable computers. I don't know if that's really a general refutation of proving new things mathematically though. The word "computer" doesn't appear once in the paper OpenAI released, nor do they make any claims specifically about "computer science": https://github.com/openai/math/blob/main/preprints/An-explic...

It's a novel bit of math. Whether or not it means anything in the context of writing software realistically is an interesting conversation, but it doesn't have much bearing on the substance of the result itself. OpenAI is pretty explicit that they view these as research results in the domain of mathematics.

The field has a lot of names. Computer science is the most common, but you can also find other names such as computing, informatics, datalogy, and data processing science (or their foreign equivalents).

Within computer science, there is a clear mathematical tradition, an engineering tradition, and a social science tradition. There are also plenty of applied computer scientists who use computer science to study topics in other fields.

yes and I'd like to sue whoever named that field for false advertising. when I went to school (Precambrian era - no internet) I thought computer science would be great because I wanted to learn how to program. I dropped it after the 2nd year when I realized it was more about calculus than programming. (and I sucked at calculus. well, the teachers who were supposed to teach me about calculus sucked, but the end result was the same.)

You care because Pierre de Fermat 16th century work on modular arithmetic was of “no intest to anyone else” except other theorists but it got to shine in the twentienth century in modern cryptography.

Doing theory is what gives you a chance to push the envelope to places you can’t even imagine when you’re knee deep in real world problems. And proving something is possible (if impractical) gives an incentive to find a better algorithm and may attract others.

For example see the first graph here: http://klotza.blogspot.com/2016/06/the-fall-of-twin-prime-ga...

I think you are free not to care about what they are doing. It turns out that big O notation has some useful properties, and in particular it is a useful definition as it allows you to define complexity classes which are a very useful tool for analyzing algorithms in general.

Much of our 'practical' understanding of algorithms also in part came from theoretical advances.

> If algorithmic theorists don't care about practical performance then why should we care about what they're doing? It's just a strange game they're playing, of no interest to anyone else.

You don't need to care. But every so often breakthroughs in theory can be turned into breakthroughs in practice.

> It seems like rather than coming up with more "galactic" algorithms, a more useful thing to do might be to come up with a replacement for big-O that's not so exploitable, and to convince theoreticians to play that game instead.

There's plenty of replacements.

Btw, we already have the optimal (in big-O terms) algorithm for every NP hard problem. We just don't know whether it runs in polynomial time or takes longer. And, yes, that algorithm called Levin's Universal Search is a galactic algorithm. Simplifying a lot, Levin's Universal Search does some clever interleaving to essentially try all possible algorithms in sort-of parallel.

Lo and behold, even the theorists you complain about don't see that 'loophole' as a solution, declare victory and go home. They still keep researching.

They do care. They also care about partial results. As of last week, we thought we knew the best possible algorithm. We now know that there's a galactic algorithm that's an asymptotic improvement. The question then becomes "Is there a non-galactic algoritm that does the same, or is any such algorithm necessarily galactic?"

The problem is that proving an algorithm is necessarily galactic is incredibly hard. If you knew how to do this, you would become one of the most celebrated complexity theorists of the age. Stanford would be calling.

Plenty of mathematics was practically useless for long periods of time, waiting for us to invent computers, cryptography, error correcting codes, etc.

It's extremely hard to know what mathematics may be useful in the future or not.

It’s unintentionally making a mockery of OpenAIs results by highlighting Blums speedup theorem in action. Namely that you can always reduce time complexity with a small move into space complexity.

That unintentional mockery of a repo is 262million lines of such moves and growing. I don’t think for a second anyone involved has a clue about complexity theory though or they’d just jump to the obvious “O(1) time complexity using an O(2^n) lookup table to cover all possible n bits of input” which is the final end state of Blums speedup theorem.

undefined

Agree, my neighbor isn’t upset about it. But he also doesn’t know mathematics