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.
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.
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.
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.
"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.
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.
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 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.
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.
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 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 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.
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.
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.
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.
Does the apply to representation of complex numbers, which is not uncountably infinite and represented by floats?
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.
Because clearly we’d have invented GPS if we had asked ourselves “how do I create a global positioning system with centimeter accuracy”?
You can't imagine how that severely limits the potential size of the discovery space shackling it to present day problems?
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.
That’s sloppy reasoning. There might be notations that allow for classifying complexity classes that don’t suffer this problem.
That may well be the case, in theory.
> 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?
"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.
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.
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
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 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.
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.
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.
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.
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 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.
> 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”
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.