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.
As a theorist, it's sort of true that I "don't care" about galactic constants. I'm interested in the structure of computation for philosophical reasons. But I really do care about the model of computation.
To put it another way, the constants inside a big-O are not really constant: they depend on what you assume is a constant-time operation.
About big-O constant, I came to the realization that in the real world, constant time is actually a log at best, but more likely a cube root.
The simple idea is that the most basic thing, that is reading the number "n" depends on the number of digits, so that's a log.
But in most algorithms, the "n" refers to the size of a data set. This set is usually stored in some kind of memory, and memory is a physical array of little cells in 3D space. Accessing that cell means travelling through the array, with a time to reach it proportional to its distance, and since capacity increases with the cube of the distance, the time it takes to get the data is proportional to the cube root of n.
The conclusion, to me, is that when complexity gets down to less than a cube root, mathematical abstractions start to break down and you need to consider the actual machine, in particular its cache architecture.
My understanding is that in the limit (i.e. before you create a black hole), information density actually scales with surface area, not volume, so square root. And then of course at that kind of density, you'd have to account for time dilation as well...
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.
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.
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.
" In 1973, Jacques Morgenstern proved that you couldn’t get a Fourier transform faster than ½ n log n if you required that complex coefficients used in the computation had bounded magnitude"
I highly doubt this is going to somehow inspire people to make faster algorithms than the mathematical bound...
I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.
>I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.
Most people getting funding for pure maths probably just lie and/or stretch the truth that it tangentially has some relation to or possible benefit to practical things like cryptography. It doesn't need to actually be true. It just needs to feel true enough.
The algorithm from OpenAI works also in prime-order finite fields. Such FFTs are used all over the place in cryptography. So clearly their result is not useless and works in a realistic computational model
I find that an extremely inefficient way of thinking. Spending time on problems on the minuscule off chance that a few centuries later they will be useful whereas you could be spending time right now on problems you know for a fact are useful is a weird trade off to make.
No, I don’t care. Until there is a real, practical result, I don’t care. There are plenty of examples of math discovered in service of solving a problem. There is nothing that says math has to be purely abstract first.
Dudeee how far up your hind do you need to be to nit even appreciate the groundwork being laid out?
Like imagine Einstein without access to geometry work. You had others point you to number theory. What about Boole's algebra.
There is a pretty big list of seemingly useless pure math things suddenly finding a very practical use. Sometimes quite a bit later too. And we have no way of knowing beforehand.
And it's fine to not want to do such work yourself. But to dismiss it is, well, not very thoughtful.
Relativity is required to explain the time dilation, but it's not needed to notice that the GPS clocks run 40µs too fast. It wouldn't take too long for them to measure enough data to create an empirical skew-versus-altitude table, which should then be enough for them to correct the time skew, even without understanding what was going on.
I think this is a difficult counterfactual to assess, we didn’t develop clock accurate enough to notice the time dilation until 50 plus years after the theory of relativity was published.
Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere? Maybe they would mothball the GPS project for not working before figuring it out? It’s hard to know, 50 years in an alternate timeline allows for a lot of domino effect
> Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere?
They probably would just assume that it's a bug at first, since "our clock is slightly broken" is far more likely than "we've discovered some cool new physics". But I don't think that that would be an issue here, since even if they thought it was a bug, they'd still try to work around it.
> Maybe they would mothball the GPS project for not working before figuring it out?
I doubt it, since if you think about all the possible issues after sending a complex untested satellite to space, a 40μs clock discrepancy is fairly minor.
I've always wondered - if special and general relativity weren't known, could the GPS engineers have just measured the error and empirically accounted for it? I don't know relativity or GPS or engineering well enough to answer.
Yes, the clock slippage is a constant factor, entirely predictable. If made public it would probably have catalyzed the discovery of special relativity soon afterwards, but then people would’ve been super confused because its predictions still wouldn’t match the observations and indeed would widen the discrepancy rather than narrowing it!
It's possible, but it seems more likely that the first tests would have shown "weird timing errors we couldnt diagnose" and then the project never got a follow up.
For something so militarily useful? When the Soviet Union was still seen as a threat to the US? When it was already so expensive anyway? I guess it's possible, but it's hard to believe they'd just give up like that.
The problem with "it's hard to believe" is that this is an area where I'm not even sure how to effectively estimate the counterposition, I've seen things that I thought were interesting get cancelled or have no follow up all the time, and it makes sense, no idea if it will matter, or even work, and even if it does, how much will it cost to realise any value?
Who knows how often really impactful tech is gated behind some non-obvious thing which we never follow up on.
I mean Douglas Engelbart basically bet his entire career behind the Mother of All Demos[0], if it had flopped, modern computing as we know it would be fundamentally different, same with Hiroo Kinoshita and Extreme Ultraviolet Lithography[1][2], we just would have had Moore's law falling off a cliff.
Yeah, absolutely. You'd be surprised how much high-precision engineering absolutely relies on "this but you have to mill a tiny amount off the end because if you do the maths it comes out ever so slightly too big, and then adjust on test".
And that's fine, caring about everything is exhausting, someone has to solve real world problem. But dismissing a result since it's not practical is not fine
How far are you willing to go? In your radical pragmatism, are you an intuitionist, or even a finitist? Oh wait, these are pure math topics that you do not care a about!
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.
The argument in the article isn’t about whether big O notation is useful it’s about whether the n in any particular big O is relevant. In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.
> In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.
Well that's certainly not the claim. Think about it, that would mean the whole thing is trivially O(1), so why would they be bothering with the rest?
You've missed part in the analysis, or I believe added an assumption they're not making (the constant-time-multiply one, specifically).
This all _is_ almost certainly impractical, but it's for the usual reason of it only being faster for numbers nobody could ever care about. It's theoretically _quite_ interesting though, because hey...what _is_ the fastest you can actually multiply numbers if it's not O(n lg n) as many ~assumed.
The complex FFT is a generalization of the n-bit integer multiplication algorithm, not the other way around. No complex-number operations are required for the integer case.
> 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.
As I read it, that was sort of their point: if the theorists were blindly focused on Big O complexity, they could 'cheat' by invoking the universal search algorithm as a good-enough solution to a huge class of problems; but they don't, because they're not mindlessly playing a game where Big O complexity is all that matters.
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.
If you read the entire argument, it makes perfect sense. It’s simultaneously mocking the poorly established ways of measuring asymptotic complexity of algorithms.
TL;DR - time complexity calculations ignore constant values. So if algorithm A takes 10^10 + n number of iterations to do something, and B does n^2, in theory B is worse, because n < n^2. But in practice, you’d be waiting a very long time for the first iteration of A to even be useful.
So in other words, time complexity gives you how well an algorithm can scale beyond the first iteration. What it doesn’t tell you is if you’d have to wait until the end of the universe to even get started.
"Malicious" is an overstatement, but "exploit" is completely fair in my view. Theory with no possible practical relevance is useless, and I think a computational complexity result requiring arbitrary-precision arithmetic that is impossible to implement using any physical system qualifies.
It's hard to know for certain, but that doesn't mean we should throw up our hands and say anything goes. We can still say that some things are more likely to be useful than others.
The idea that FFT's decomposition is non-optimal is surprising. What the new bound means is we basically were looking at the problem and its structure incorrectly, and therefore implicates other problems for which we have used recursion to get to our currently-best bounds.
Almost no interesting math problems are just sitting there alone in their little corner. Getting a hint like that is a big deal.
Is it surprising though? If you assume constant time when it doesn't exist (in this case arbitrary precision arithmetic), it should be obvious that you will be able to devise algorithms that are faster than the commonly accepted best results.
If you can do arithmetic on arbitrarily large integers in constant time, you can sort lists in linear time.
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
I don't think that is necessarily true, the post is making a stronger point than what you describe
> Indeed, the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n. If you stored these numbers as bits, the memory requirement would effectively be exponential in the input length. It assumes you can multiply such arbitrarily large complex numbers together in a single operation.
Another way to think about what the author said, imagine you had access to an oracle which could execute arbitrary precision arithmetic expressions in constant time. You could encode a wide range of computations in these and execute impossible algorithms.
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.
Are you certain that applies here? The length of the intermediate numbers grows superpolynomially, so you would be sure to overflow fixed width numbers. Floats are not a field.
Yes, floats are not a field, which is why you don't use floating point except to convert to and from a different representation. Overflow is expected and cancels out as long as the final result is uniquely representable. See the paper I linked, which implements 64-bit floating point matrix multiplication using 8-bit numbers with wrapping overflow modulo a set of small coprime integers. The result is reconstructed at the end using the Chinese Remainder Theorem.
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.
It's worse case linear, as used for sorting it beats the Go standard library on the average and worst cases, lagging a bit on the best cases.
In my experience, median-on-ninthers (which is only slightly more complicated than median-of-medians) definitely beats both heap sort and particularly heap select as a fall back for the degenerate case.
And it's not just academic: I've sped up significant stuff at work by switching from sorting to partial sorting and/or selection.
The irony being Dijkstra had lots of deep ideas about how programming ought to be done (from a basic science approach as informed by CS) and that the industry is still in the stone/bronze ages in terms of putting advanced ideas into practice.
A lovely theory, and yet the field is called "computer science".
Also, while I am not an expert, I suspect it is frequently useful to understand how telescopes actually work when you're trying to do astronomy with them.
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.)
It is a misnomer because it's not really about computers, nor is it science (although machine learning has always been much more scientific IMO). But it is about programming. It's just from first principles. It's like learning to build furniture: you first have to learn about wood. Sure, most people will just put something together from IKEA, and that might be satisfying. But they don't really know how to build furniture.
I'm confused by some of the reactions here. Isn't this the first step toward taking theory into reality? So, FT could be faster if we could multiply larger numbers. The problem has now moved from is it possible to "do we have the hardware to do it?" Not my area, so maybe someone could explain to me why this isn't a question of how large the instruction limit is right now? Would 128bit systems change this meaningfully?
No, not in this case. The assumption of unit cost arithmetic is simply not physically realizable. It's probably easier to understand the integer case: numbers take bits to store and represent. In a typical computer, you would store numbers as either 32 or 64 bits, where 32 bits could store a number up to about 4 billion (or a signed number between -2 and +2 billion). If you want to store and multiply numbers larger than that, they take up more space and they require more work on the part of the processor, and fundamentally, more energy - adding two 128 bit numbers takes twice the work as adding two 64 bit numbers.
The same applies to the precision of floating point numbers. What Ben is arguing is happening in this case is the AI has found a way to hide work by moving it into operations that, in one (unrealistic) model of computation, are assumed to cost the same regardless of how large or precise the numbers are. Other models of computation have a more accurate model of the cost of these things, but that was not the model the AI chose to apply in this case.
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.
No, I don't think you (or the part of the thread I read thus far, top to bottom) are giving the most charitative interpretation of the post.
In my understanding, the article wants to raise awareness of the potential dynamics of a mathematics/theoretical computer science field governed by the imperfect rules (as they must be) of human sensemaking when the merit system (publication and community standards) are hacked by a machines for which the cost-benefit calculation is very different than for human reseachers for which the rules were invented / sedimented in the first place.
The foregoing discussion above about the emergent utility of now seemingly wasteful theoretical research is as old as any other, but equally predicated on human effort/apability ratios. And AI should invite us to rethink, because to be relevant to humans, its unwieldy results will have to be judged by humans, on their timescales and effort budgets. So we are discussing whether SPAM or HAM before we literally spend our lives as human critics of what ultimately could just be a reward hacking exercise by somebody with access to free tokens.
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.
And exact arithmetic on Q + i*Q (complex numbers but the coordinates are rational numbers, not real numbers) is perfectly feasible.
Of course, in a real computer, long rational numbers take longer to manipulate than short rational numbers. But it's just a model. Similar to how we often assume we can handle arbitrary integers in unit time, but in reality longer integers also take longer to handle on a real computer (or we just refuse to handle them and stick to u64 only.)
Either a model can be wrong or it is just a model. If it's the former, it matters whether Turing machines are less wrong than exact complex arithmetic machines.
There is, of course, the very rich field of Numerical Analysis which deals with how we actually represent these things in real life, but for a starting point assuming this sort of thing is par for the course.
So, the pseudo-FFT exploits algorithmic similarity between DFT and multiplication to translate part of the DFT work into multiplication work, which is O(1) in the exact arithmetic model.
Thus, the magnitudes of the numbers being multiplied grow superpolynomially with n (the DFT problem size): because the robot's stuffing its work in there and using it as an oracle.
I am astounded by the activity in this repo... what is going on? 508 PRs on 408 commits..? It's getting additions at a frenetic pace by a large number of contributors.
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.
> Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I? I did what every other mathematician in the world does with AI slop mathematics: I fed it back into the slop machine and ran an information retrieval session with a chatbot interface to extract salient facts. Anthropomorphically speaking: I asked ChatGPT what it thinks about its own output. This is how we do mathematical research now. What a world.
> The theory of computer science has become a form of mathematics that doesn’t concern itself with computers
Perfectly summarizes the post, which I'd qualify as a rant (the author's main gripe seems to be that it's a galactic algorithm that assumes exact complex multiplication). The theory of computer science literally started with a mathematical model by Alan Turing that has nothing to do with computers (ones that we could physically build, anyway; and even if we brush aside the infinite tape, it's just architecturally completely different from any computers we've ever built for practical purposes).
If you don't like mathematics without direct applicability, you do you, but it's a legitimate mathematical undertaking and cheap way to rant against this AI drop. Do the work and show us if there's a mistake in the argument, missing attribution or whatever actual problems with the paper, but spare us your sour grapes.
I can't speak for the FFT claim, but least the sub-O(n log n) multiplication claim is for the multitape Turing machine model with a fixed number of tapes, which if anything is more restrictive than actual random-access memory. Of course, it's still galactic just like the O(n log n) algorithm, but it definitely seems like there's something there.
> 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:
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.
> AI seems to be very good at getting answers, but not always answers to the correct questions.
I don't think that's an accurate summary of the article you linked. The Lean proof solved the exact problem it was supposed to, it just had minor discrepancies from the writeup of the proof (on the level of saying a theorem requires m+4 derivatives when it actually requires m+5 derivatives). Obviously a problem but not really a bombshell.
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
I think it's reasonable to give the benefit of the doubt to humans, but not LLMs, that their galactic constants are not just attempts to "hack" the problem description. If LLMs are going to turn up a bunch of them, we have to develop a better version of complexity theory that accounts for them.
> “The model uses exact complex arithmetic.” That means it assumes you can store and multiply complex numbers at arbitrary precision. Indeed, the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n.
This in particular is the kind of thing that I'd expect a human would at least pause on and ideally note as a severe caveat to any claimed asymptotic improvement. I don't know off the top of my head if the story is as simple as "you can tuck part of the asymptote into your presumed constant arithmetic", but it sounds kinda plausible?
This article has basically nothing to do with the OpenAI paper; it's a critique of the entire field of computer science, rehashed to pick at one of their papers.
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.
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.
i resolved this a coder with adding math symbols to my keyboard.
When you can start doing A₁₂ ⟨M⟩₃† (complete made up nonsense) in your code or just comments without going latex etc it comes more naturally as you wont have to switch context so often.
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.
And people's love of AI is also surfacing their dislike of pure mathematicians. Plenty of comments along the lines of "turns out mathematicians were just idiot savants solving puzzles".
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.
As a theorist, it's sort of true that I "don't care" about galactic constants. I'm interested in the structure of computation for philosophical reasons. But I really do care about the model of computation.
To put it another way, the constants inside a big-O are not really constant: they depend on what you assume is a constant-time operation.
About big-O constant, I came to the realization that in the real world, constant time is actually a log at best, but more likely a cube root.
The simple idea is that the most basic thing, that is reading the number "n" depends on the number of digits, so that's a log.
But in most algorithms, the "n" refers to the size of a data set. This set is usually stored in some kind of memory, and memory is a physical array of little cells in 3D space. Accessing that cell means travelling through the array, with a time to reach it proportional to its distance, and since capacity increases with the cube of the distance, the time it takes to get the data is proportional to the cube root of n.
The conclusion, to me, is that when complexity gets down to less than a cube root, mathematical abstractions start to break down and you need to consider the actual machine, in particular its cache architecture.
My understanding is that in the limit (i.e. before you create a black hole), information density actually scales with surface area, not volume, so square root. And then of course at that kind of density, you'd have to account for time dilation as well...
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.
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.
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...
Considering this line:
" In 1973, Jacques Morgenstern proved that you couldn’t get a Fourier transform faster than ½ n log n if you required that complex coefficients used in the computation had bounded magnitude"
I highly doubt this is going to somehow inspire people to make faster algorithms than the mathematical bound...
I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.
>I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.
Most people getting funding for pure maths probably just lie and/or stretch the truth that it tangentially has some relation to or possible benefit to practical things like cryptography. It doesn't need to actually be true. It just needs to feel true enough.
It's like all the robotics works that obviously might be applicable to Search and Rescue and help firemen fight fires.
Does the apply to representation of complex numbers, which is not uncountably infinite and represented by floats?
Yes. It applies to "linear algorithms", which are basically functions of the form
where each ti is a linear combination of previous t vars, inputs x vars, or constants.The cost model is just the number of additions performed.
The algorithm from OpenAI works also in prime-order finite fields. Such FFTs are used all over the place in cryptography. So clearly their result is not useless and works in a realistic computational model
I find that an extremely inefficient way of thinking. Spending time on problems on the minuscule off chance that a few centuries later they will be useful whereas you could be spending time right now on problems you know for a fact are useful is a weird trade off to make.
No, I don’t care. Until there is a real, practical result, I don’t care. There are plenty of examples of math discovered in service of solving a problem. There is nothing that says math has to be purely abstract first.
Dudeee how far up your hind do you need to be to nit even appreciate the groundwork being laid out?
Like imagine Einstein without access to geometry work. You had others point you to number theory. What about Boole's algebra.
There is a pretty big list of seemingly useless pure math things suddenly finding a very practical use. Sometimes quite a bit later too. And we have no way of knowing beforehand.
And it's fine to not want to do such work yourself. But to dismiss it is, well, not very thoughtful.
Because clearly we’d have invented GPS if we had asked ourselves “how do I create a global positioning system with centimeter accuracy”?
That is how we invented GPS...
And without relativity theory positioning error would be measured in kilometers.
Relativity is required to explain the time dilation, but it's not needed to notice that the GPS clocks run 40µs too fast. It wouldn't take too long for them to measure enough data to create an empirical skew-versus-altitude table, which should then be enough for them to correct the time skew, even without understanding what was going on.
I think this is a difficult counterfactual to assess, we didn’t develop clock accurate enough to notice the time dilation until 50 plus years after the theory of relativity was published.
Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere? Maybe they would mothball the GPS project for not working before figuring it out? It’s hard to know, 50 years in an alternate timeline allows for a lot of domino effect
> Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere?
They probably would just assume that it's a bug at first, since "our clock is slightly broken" is far more likely than "we've discovered some cool new physics". But I don't think that that would be an issue here, since even if they thought it was a bug, they'd still try to work around it.
> Maybe they would mothball the GPS project for not working before figuring it out?
I doubt it, since if you think about all the possible issues after sending a complex untested satellite to space, a 40μs clock discrepancy is fairly minor.
I've always wondered - if special and general relativity weren't known, could the GPS engineers have just measured the error and empirically accounted for it? I don't know relativity or GPS or engineering well enough to answer.
Yes, the clock slippage is a constant factor, entirely predictable. If made public it would probably have catalyzed the discovery of special relativity soon afterwards, but then people would’ve been super confused because its predictions still wouldn’t match the observations and indeed would widen the discrepancy rather than narrowing it!
It's possible, but it seems more likely that the first tests would have shown "weird timing errors we couldnt diagnose" and then the project never got a follow up.
For something so militarily useful? When the Soviet Union was still seen as a threat to the US? When it was already so expensive anyway? I guess it's possible, but it's hard to believe they'd just give up like that.
The problem with "it's hard to believe" is that this is an area where I'm not even sure how to effectively estimate the counterposition, I've seen things that I thought were interesting get cancelled or have no follow up all the time, and it makes sense, no idea if it will matter, or even work, and even if it does, how much will it cost to realise any value?
Who knows how often really impactful tech is gated behind some non-obvious thing which we never follow up on.
I mean Douglas Engelbart basically bet his entire career behind the Mother of All Demos[0], if it had flopped, modern computing as we know it would be fundamentally different, same with Hiroo Kinoshita and Extreme Ultraviolet Lithography[1][2], we just would have had Moore's law falling off a cliff.
-[0]: [The Mother of All Demos, presented by Douglas Engelbart (1968)](https://www.youtube.com/watch?v=yJDv-zdhzMY)
-[1]: https://spie.org/news/photonics-focus/mayjune-2023/developin...
-[2]: [The Closest Thing We Have to Alien Technology by Veritasium](https://www.youtube.com/watch?v=MiUHjLxm3V0)
Yeah, absolutely. You'd be surprised how much high-precision engineering absolutely relies on "this but you have to mill a tiny amount off the end because if you do the maths it comes out ever so slightly too big, and then adjust on test".
doesn't it use special relativity or some modern physics?
And that's fine, caring about everything is exhausting, someone has to solve real world problem. But dismissing a result since it's not practical is not fine
You can't imagine how that severely limits the potential size of the discovery space shackling it to present day problems?
I think the poster is distinguishing between currently practical and ever practical. Galactic algorithms can never be realized.
The constants can be made lower. If we didn't know about the galactic algorithm beforehand, we couldn't begin to do that.
Ironic username as I doubt we'd get to the stars with your philosophy.
How far are you willing to go? In your radical pragmatism, are you an intuitionist, or even a finitist? Oh wait, these are pure math topics that you do not care a about!
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.
The argument in the article isn’t about whether big O notation is useful it’s about whether the n in any particular big O is relevant. In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.
> In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.
Well that's certainly not the claim. Think about it, that would mean the whole thing is trivially O(1), so why would they be bothering with the rest?
You've missed part in the analysis, or I believe added an assumption they're not making (the constant-time-multiply one, specifically).
This all _is_ almost certainly impractical, but it's for the usual reason of it only being faster for numbers nobody could ever care about. It's theoretically _quite_ interesting though, because hey...what _is_ the fastest you can actually multiply numbers if it's not O(n lg n) as many ~assumed.
The complex FFT is a generalization of the n-bit integer multiplication algorithm, not the other way around. No complex-number operations are required for the integer case.
That’s sloppy reasoning. There might be notations that allow for classifying complexity classes that don’t suffer this problem.
your reasoning is sloppy. so confidently incorrect throughout this thread!
You're free to propose one and see if it catches on
That may well be the case, in theory.
There might not be, how is your reasoning any less “sloppy”?
> 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.
If Big-O lets you run every possible algorithm in "parallel" while still being in some sense "optimal," that seems like yet another exploit?
As I read it, that was sort of their point: if the theorists were blindly focused on Big O complexity, they could 'cheat' by invoking the universal search algorithm as a good-enough solution to a huge class of problems; but they don't, because they're not mindlessly playing a game where Big O complexity is all that matters.
Yes, exactly. I'm afraid I didn't make myself very clear. Thanks for explaining it better than I did.
It's not an exploit, it's a gap in our understanding of the algorithms. We know it's optimal, but we don't know the Big-O complexity.
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.
If you read the entire argument, it makes perfect sense. It’s simultaneously mocking the poorly established ways of measuring asymptotic complexity of algorithms.
TL;DR - time complexity calculations ignore constant values. So if algorithm A takes 10^10 + n number of iterations to do something, and B does n^2, in theory B is worse, because n < n^2. But in practice, you’d be waiting a very long time for the first iteration of A to even be useful.
So in other words, time complexity gives you how well an algorithm can scale beyond the first iteration. What it doesn’t tell you is if you’d have to wait until the end of the universe to even get started.
"Malicious" is an overstatement, but "exploit" is completely fair in my view. Theory with no possible practical relevance is useless, and I think a computational complexity result requiring arbitrary-precision arithmetic that is impossible to implement using any physical system qualifies.
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 hard to know for certain, but that doesn't mean we should throw up our hands and say anything goes. We can still say that some things are more likely to be useful than others.
The idea that FFT's decomposition is non-optimal is surprising. What the new bound means is we basically were looking at the problem and its structure incorrectly, and therefore implicates other problems for which we have used recursion to get to our currently-best bounds. Almost no interesting math problems are just sitting there alone in their little corner. Getting a hint like that is a big deal.
Is it surprising though? If you assume constant time when it doesn't exist (in this case arbitrary precision arithmetic), it should be obvious that you will be able to devise algorithms that are faster than the commonly accepted best results.
If you can do arithmetic on arbitrarily large integers in constant time, you can sort lists in linear time.
How can we say that without knowing the future?
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
I don't think that is necessarily true, the post is making a stronger point than what you describe
> Indeed, the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n. If you stored these numbers as bits, the memory requirement would effectively be exponential in the input length. It assumes you can multiply such arbitrarily large complex numbers together in a single operation.
Another way to think about what the author said, imagine you had access to an oracle which could execute arbitrary precision arithmetic expressions in constant time. You could encode a wide range of computations in these and execute impossible algorithms.
This reminds me of 'O(1)' hash maps, but far more egregious.
What's wrong with `O(1)` hash maps? I'm not aware of any underhanded tricks related to, for example, cuckoo hashing.
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.
Are you certain that applies here? The length of the intermediate numbers grows superpolynomially, so you would be sure to overflow fixed width numbers. Floats are not a field.
Yes, floats are not a field, which is why you don't use floating point except to convert to and from a different representation. Overflow is expected and cancels out as long as the final result is uniquely representable. See the paper I linked, which implements 64-bit floating point matrix multiplication using 8-bit numbers with wrapping overflow modulo a set of small coprime integers. The result is reconstructed at the end using the Chinese Remainder Theorem.
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.
> "median of medians" (finding the median in a list in O(n) worst-case time) is useless because it is not used in practice.
This one is just not true. Here it is in 255 lines of well commented Go code: https://github.com/ncruces/sort/blob/v1.0.3/quick/quick.go
It's worse case linear, as used for sorting it beats the Go standard library on the average and worst cases, lagging a bit on the best cases.
In my experience, median-on-ninthers (which is only slightly more complicated than median-of-medians) definitely beats both heap sort and particularly heap select as a fall back for the degenerate case.
And it's not just academic: I've sped up significant stuff at work by switching from sorting to partial sorting and/or selection.
https://en.wikipedia.org/wiki/Galactic_algorithm for those not in the know.
The irony being Dijkstra had lots of deep ideas about how programming ought to be done (from a basic science approach as informed by CS) and that the industry is still in the stone/bronze ages in terms of putting advanced ideas into practice.
If after endless amounts of advocacy, industry still hasn't adopted it, then the problem is with Dijkstra's theory and not with industry.
A lovely theory, and yet the field is called "computer science".
Also, while I am not an expert, I suspect it is frequently useful to understand how telescopes actually work when you're trying to do astronomy with them.
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.)
It is a misnomer because it's not really about computers, nor is it science (although machine learning has always been much more scientific IMO). But it is about programming. It's just from first principles. It's like learning to build furniture: you first have to learn about wood. Sure, most people will just put something together from IKEA, and that might be satisfying. But they don't really know how to build furniture.
I'm confused by some of the reactions here. Isn't this the first step toward taking theory into reality? So, FT could be faster if we could multiply larger numbers. The problem has now moved from is it possible to "do we have the hardware to do it?" Not my area, so maybe someone could explain to me why this isn't a question of how large the instruction limit is right now? Would 128bit systems change this meaningfully?
No, not in this case. The assumption of unit cost arithmetic is simply not physically realizable. It's probably easier to understand the integer case: numbers take bits to store and represent. In a typical computer, you would store numbers as either 32 or 64 bits, where 32 bits could store a number up to about 4 billion (or a signed number between -2 and +2 billion). If you want to store and multiply numbers larger than that, they take up more space and they require more work on the part of the processor, and fundamentally, more energy - adding two 128 bit numbers takes twice the work as adding two 64 bit numbers.
The same applies to the precision of floating point numbers. What Ben is arguing is happening in this case is the AI has found a way to hide work by moving it into operations that, in one (unrealistic) model of computation, are assumed to cost the same regardless of how large or precise the numbers are. Other models of computation have a more accurate model of the cost of these things, but that was not the model the AI chose to apply in this case.
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.
No, I don't think you (or the part of the thread I read thus far, top to bottom) are giving the most charitative interpretation of the post.
In my understanding, the article wants to raise awareness of the potential dynamics of a mathematics/theoretical computer science field governed by the imperfect rules (as they must be) of human sensemaking when the merit system (publication and community standards) are hacked by a machines for which the cost-benefit calculation is very different than for human reseachers for which the rules were invented / sedimented in the first place.
The foregoing discussion above about the emergent utility of now seemingly wasteful theoretical research is as old as any other, but equally predicated on human effort/apability ratios. And AI should invite us to rethink, because to be relevant to humans, its unwieldy results will have to be judged by humans, on their timescales and effort budgets. So we are discussing whether SPAM or HAM before we literally spend our lives as human critics of what ultimately could just be a reward hacking exercise by somebody with access to free tokens.
Yes, this is clickbait. The author does not like the definition of big-O. OpenAI is just a scapegoat.
> The author does not like the definition of big-O
Nobody really likes the definition of Big-O. It's been unmoored from actual computing performance ever since caches were invented...
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.
Almost no one uses Turing machines for complexity theory.
At most you use them for stuff like P vs NP, because Turing machines are 'only' polynomially slower than register machines, so it doesn't matter.
But when you are talking about linear vs quadratic on something resembling real computers, Turing machines are the wrong model.
So what? Using something that can carry out "exact complex arithmetic" is even more wrong.
Why? It's just a model.
And exact arithmetic on Q + i*Q (complex numbers but the coordinates are rational numbers, not real numbers) is perfectly feasible.
Of course, in a real computer, long rational numbers take longer to manipulate than short rational numbers. But it's just a model. Similar to how we often assume we can handle arbitrary integers in unit time, but in reality longer integers also take longer to handle on a real computer (or we just refuse to handle them and stick to u64 only.)
> Turing machines are the wrong model.
> Why? It's just a model.
Either a model can be wrong or it is just a model. If it's the former, it matters whether Turing machines are less wrong than exact complex arithmetic machines.
This kind of this is pretty common (see, for example https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...).
There is, of course, the very rich field of Numerical Analysis which deals with how we actually represent these things in real life, but for a starting point assuming this sort of thing is par for the course.
No, it’s unusual to use Turing machines as the model.
Turing machines are good for computability but not great for complexity.
So, the pseudo-FFT exploits algorithmic similarity between DFT and multiplication to translate part of the DFT work into multiplication work, which is O(1) in the exact arithmetic model.
Thus, the magnitudes of the numbers being multiplied grow superpolynomially with n (the DFT problem size): because the robot's stuffing its work in there and using it as an oracle.
Did I get that much right? What a cool hack.
Declaring your most expensive operation to be O(1) is the oldest trick in the book for shrinking problem bounds
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
What is this repository?
I've just opened a random Python script and it... just replaces a bunch of text in latex files? Why?
https://github.com/CrocSwap/integer-mult-bounds/blob/main/sc...
Is this like post-modern performance art?
I am astounded by the activity in this repo... what is going on? 508 PRs on 408 commits..? It's getting additions at a frenetic pace by a large number of contributors.
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.
The input is unlimited size and the algorithm is achieving a speedup with constant size code.
This made me chortle:
> Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I? I did what every other mathematician in the world does with AI slop mathematics: I fed it back into the slop machine and ran an information retrieval session with a chatbot interface to extract salient facts. Anthropomorphically speaking: I asked ChatGPT what it thinks about its own output. This is how we do mathematical research now. What a world.
That should have been the gate all along. Not "You didn't write it, so why should I read it?" [0] but "You didn't even read it, so why should I?"
[0] https://news.ycombinator.com/item?id=49794330
> The theory of computer science has become a form of mathematics that doesn’t concern itself with computers
Perfectly summarizes the post, which I'd qualify as a rant (the author's main gripe seems to be that it's a galactic algorithm that assumes exact complex multiplication). The theory of computer science literally started with a mathematical model by Alan Turing that has nothing to do with computers (ones that we could physically build, anyway; and even if we brush aside the infinite tape, it's just architecturally completely different from any computers we've ever built for practical purposes).
If you don't like mathematics without direct applicability, you do you, but it's a legitimate mathematical undertaking and cheap way to rant against this AI drop. Do the work and show us if there's a mistake in the argument, missing attribution or whatever actual problems with the paper, but spare us your sour grapes.
> 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 can't speak for the FFT claim, but least the sub-O(n log n) multiplication claim is for the multitape Turing machine model with a fixed number of tapes, which if anything is more restrictive than actual random-access memory. Of course, it's still galactic just like the O(n log n) algorithm, but it definitely seems like there's something there.
You can be linear in the bit length of the input number, but exponential in the magnitude.
This is a common thing in complexity, and I think even the abstract says it is talking about “length n” and not “magnitude n”
> 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.
> AI seems to be very good at getting answers, but not always answers to the correct questions.
I don't think that's an accurate summary of the article you linked. The Lean proof solved the exact problem it was supposed to, it just had minor discrepancies from the writeup of the proof (on the level of saying a theorem requires m+4 derivatives when it actually requires m+5 derivatives). Obviously a problem but not really a bombshell.
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
A lot of people are emphatically NOT upset about the OpenAI math dump.
Agree, my neighbor isn’t upset about it. But he also doesn’t know mathematics
I think it's reasonable to give the benefit of the doubt to humans, but not LLMs, that their galactic constants are not just attempts to "hack" the problem description. If LLMs are going to turn up a bunch of them, we have to develop a better version of complexity theory that accounts for them.
> “The model uses exact complex arithmetic.” That means it assumes you can store and multiply complex numbers at arbitrary precision. Indeed, the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n.
This in particular is the kind of thing that I'd expect a human would at least pause on and ideally note as a severe caveat to any claimed asymptotic improvement. I don't know off the top of my head if the story is as simple as "you can tuck part of the asymptote into your presumed constant arithmetic", but it sounds kinda plausible?
> Human algorithm researchers have been publishing those sorts of results for decades now
This is a superfluous remark because the article already said it. He criticizes theoretical computer science for doing it, not just OpenAI.
This article has basically nothing to do with the OpenAI paper; it's a critique of the entire field of computer science, rehashed to pick at one of their papers.
Wake me up when someone has understood the proof.
"…nothing to do with the OpenAI paper; it's a critique of the entire field of computer science…"
That field being exacerbated by the deluge of OpenAI papers. There is a pretty direct tie-in.
I expect though it will be the theoretical computer scientists that we'll hear the most from in the coming days/years in this new era of LLM papers.
> it's a critique of the entire field of computer science
A good one though. A theoretical computer science which researchs "algorithms" which are impossible to run on a real computer has gone astray.
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.
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.
i resolved this a coder with adding math symbols to my keyboard.
When you can start doing A₁₂ ⟨M⟩₃† (complete made up nonsense) in your code or just comments without going latex etc it comes more naturally as you wont have to switch context so often.
https://krei.se/Doc/hardware/003-xkb-Keyboardflow
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.
And people's love of AI is also surfacing their dislike of pure mathematicians. Plenty of comments along the lines of "turns out mathematicians were just idiot savants solving puzzles".
I have seen no despisal just a bit of a dismissal which was always there
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.