A look at OpenAI’s math that’s claimed computes faster Fourier transforms

The author is attacking the field of theoretical algorithm design broadly as being useless. If we take the author's logic to its conclusion, many algorithms we learn about in a standard Algorithm Design course such as "median of medians" (finding the median in a list in O(n) worst-case time) is useless because it is not used in practice. Even the original 2019 Harvey–van der Hoeven result, showing integration multiplication can be done in O(n log n), has a galactic overhead and no applications.

> theory gets so unmoored from the original question that an “open problem” becomes nothing more than an academic status puzzle...The theory of computer science has become a form of mathematics that doesn’t concern itself with computers, and it offers little reward for impact outside those mathematical pursuits

I thought it is common knowledge (and a common warning from profs to first-year CS students) that computer science has very little to do with computers. The very concept of Turing machines and decidability are mathematical in nature, far removed from how computers these days are run. The undecidability of Wang tiling, for example, is definitely a notable CS result, but it has nothing to do with computers." It is essentially a branch of mathematics. "Computer Science Is Not About Computers, Any More Than Astronomy Is About Telescopes" is a famous quote attributed to Dikstra. There is even famous MIT Open Courseware clip: https://youtu.be/2Op3QLzMgSY?t=30

This is a bad take. I will happily acknowledge the new term "slopository" which I had not heard before, while taking the author to task for malice towards theorists. STOC/FOCS/SODA, etc are not about "doing practical algorithms". If you want that, you go to ESA, ALENEX, or VLDB/SIGMOD, or any of the other more applied venues featuring this work. I don't think it's fair to just shit on theory because they don't do experiments---they're mathematicians, and it is fine to have absurd constants in your big-O as long as they are constants.

PS. I can have this view while simultaneously thinking that Ben is a badass.

The author could have left AI entirely out of the essay and come to the same conclusions. He just really doesn't like TCS. That's fine, it's really a part of mathematics not science, but it's silly to dismiss a field with "theoretical" in its name for being impractical.

Did not realize that the model of computation for all of the banner computational complexity results from last week was "exact complex arithmetic." Is this and/or "exact real arithmetic" a common premise for papers in this field? My assumption as an outsider was that people mostly care about things equivalent to Turing machines.

edit: by "things equivalent to" I really mean universal register machines, something that operates on integers and not directly on real numbers.

There is currently an effort underway to improve the bound. They have reached at a much larger kappa around 0.001635527380375392

https://github.com/CrocSwap/integer-mult-bounds

To be honest this reminds me of interview leetcode. Like I remember one where you could get constant time if you made nested hashtables covering character sequences that might have made sense in USCII but probably would be impossible to maintain in UTF. In general leetcode problems love goading you to treat the ASCII character space as constant time to deal with and it's stupid. And it seems very similar to this.

> This new OpenAI result is thus less a mathematical breakthrough and more an oddity of computer scientists being bad at formalizing their design specifications.

Related, another article about proofs that may depend on bad formalizations:

https://news.ycombinator.com/item?id=49994145 - Navier-Stokes Lost in Translation (5 days ago, 237 comments)

AI seems to be very good at getting answers, but not always answers to the correct questions. These remind me of Deep Thought from The Hitchhiker's Guide to the Galaxy, where they got an answer to the ultimate question before actually knowing what the ultimate question is.

I am as upset as the slew of math slop from OpenAI as the next guy, but I do not understand this article. Are they saying that this was not a true improvement because the algorithm is _galactic_? Human algorithm researchers have been publishing those sorts of results for decades now

An unpleasant part of the AI math revolution is that people's hatred of AI is bringing to bear their hatred of pure mathematics in general. I've always known in the back of my mind that mathematicians were secretly despised and looked down upon by many, but it's a bad feeling to see it become so mainstream.

> the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n.

Err... doesn't that completely invalidate the big-O analysis!?

I suspected that these Open AI "proofs" of sub-nlogn times were cheating somehow, by sweeping something under a rug. This seems to be it!

I Fairly know about FFT, its an algorithm of DFT.

As the argmin suggests Writing computational complexity in Big O isn't great here.

since we generally see the interms of no.of complex additions and no.of Multiplications in the FFT algorithm.

I’ve made some half hearted attempts to try and understand even the framing of some of these problems that were solved, and my god theoretical math is hard. It’s completely impenetrable with unknown symbols and hard to comprehend bounds and several orders of derivatives. It’s all unintuitive to me.