<- Back
Comments (121)
- p11pThis 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.
- phoenixreaderThe 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 pursuitsI 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
- perching_aix[delayed]
- senderistaThe 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.
- scuppernongDid 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.
- chapmanclI'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?
- peri-clSo, 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.
- itissidThere is currently an effort underway to improve the bound. They have reached at a much larger kappa around 0.001635527380375392https://github.com/CrocSwap/integer-mult-bounds
- fergieThis 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.
- c7b> The theory of computer science has become a form of mathematics that doesn’t concern itself with computersPerfectly 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.
- jiggawatts> 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!
- omoikane> 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.
- agnishomI 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
- GlyptodonTo 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.
- qnleighThis 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.
- dyauspitrI’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.
- traesAn 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.
- anonundefined
- Regex777I 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.