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.
"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.
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...
"Information density" is a ratio, i.e. the ratio between the amount of information and the length, area or volume in which it is stored, so it does not "scale".
The amount of information at high enough amounts scales with the volume in which it is stored.
Because of the need to be able to reach the cells that store information, the density of information is normally high in 2 directions an low in the 3rd direction.
This is why it is useful to distinguish between the density of information per area, which is determined by things like the size of a magnetic head or the resolution of a photolithographic process, and the density of information per volume, which is determined by the density of information per area and by some kind of layer thickness, which is usually determined by mechanical considerations, e.g. to ensure enough strength for a tape or a disk or an integrated circuit package.
Like I have said, at high enough amounts of information you reach an almost constant information density per volume, like in a rack full with HDDs or in a magnetic tape robotic library.
Not that I'm an expert here but my understanding is that information does not scale with the volume in which it is stored; it scales with the surface area of the event horizon it creates (at least for an electrically neutral, non-rotating black hole). Is that incorrect?
No, memory reads do not depend on the address distance, unless you create a list.
Ordinary memory is not a list. It's a flat space read in O(1).
In theory. In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
So if your entire data structure lives in cache and you repeatedly loop through it, it's going to be processed much more quickly than a bigger and more spread-out structure.
There's also paging, and alloc/dealloc to consider, and maybe garbage collection.
By the time you include all of that big-O estimates can become wildly misleading generalisations, unless your n is always >a million or so.
They mean physical distance, not "address distance".
And in the general case, memory reads do depend on distance. Hence:
> In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
This is why we have the cache levels in the first place. And the hierarchy continues: L1, L2, RAM, block of spinning rust in the closet, "the cloud" somewhere... There is only so much storage you can fit close to core! More = physically bigger = physically further away.
Sure, within a level might feel like constant time. But that's because the optimal case for that level is slowed down to match the suboptimal cases. The step discontinuities in access time are caused by our inability to engineer a system to manage this tradeoff continuously, not a fundamental law.
Cache is not fast because it's physically close to the core. Well okay, closeness does matter but it doesn't matter as much as the fact that cache is static, i.e. it's (effectively) made of flip-flops.
If you build a computer with DRAM 10 cm away from the CPU and static RAM 50 cm away, access times for the static RAM will still be much lower than the DRAM.
Why don't we just build all RAM as static? Because it's more expensive per bit, it uses more energy, and it requires a great deal more silicon area.
When we are talking about galactic algorithms we have long since left the realm of things that might fit on one computer. Some of these algorithms are only starting to become faster on n so large that we have trouble fitting the data in this solar system. At those scales the distinction between the type of RAM is irrelevant. At that point "how long to read memory address X" is pretty much the same as "how long does light take to reach X" which is pretty much "how far to X" which scales with a cube root. (Well, probably a square root if we look at physical limits for weird reasons)
Some of the computation models (including the ones in some of the OpenAI papers in question) avoid this particular concern by working in a multi-tape Turing machine model. One might quibble about the energy cost of moving an entire infinite tape (because it’s multi-tape and, for bounded communication code, the heads need to stay near each other), but the machines really are local in a fairly strong sense.
I contemplated the article and it occurred to me that integer matrix multiplication is probably O(n^2), without even any galactic constants. But it will need unit-cost integer math.
First, find a sufficiently large base b so that no intermediate calculation exceeds b-1 (one pass over the matrices should do the trick). Then encode each row of the left matrix as a big value A_i = sum_k a_ik * b^k. Encode each column of the the right matrix as B_j = sum_k b_kj * b^(n-k). Compute A and B explicitly (takes O(n^2) integer operations).
Now you extract the answer one element at a time. A_i * B_j has a bunch of terms including sum_k a_ik * b_kj * b^n. All other terms have different powers of b. So do an integer division by b^(n-1), discard the remainder, then take the result mod b, and that gives (a*b)_ij, costing one integer multiplication and two divmod operations per output element. Problem solved. Can I publish in FOCS?
This is, of course, a wild cheat: even with OpenAI’s latest and greatest galactic integer multiplication algorithm, this is slower than the plain high school matrix multiplication algorithm on any real computer.
I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)
I haven't come up with anything using natural integer operations. I can come up with really disgusting hacks using highly unnatural integer operations, but that feels too gross to even include in this category of cheats -- if you're willing to use unit-costs unnatural integer operations, then you might as well give up: you can do literally any operation on inputs that can be kludged into a integer in constant time.
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.
Youre just repeating the argument made in the blog without responding to the poster who said the argument is bad. Not wrong, bad. If you want to say theory is useless, do it.
Did not realize that the model of computation for all of the banner computational complexity results 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.
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.
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.
No, because in the model of computation they're using, you can multiply any two numbers in constant time. See https://enwp.org/Real_RAM for a similar model.
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 above 2^n is just the extreme. There’s always baby steps to that direction. If you want you can point an agent at any known nlogn algorithm (eg. Sorting) and quickly get similar improvements in a similar way.
The most trivial example of a baby step there is to have a lookup table for every kth element. That alone gets you below nlogn for any existing nlogn algorithm at the expense of storage complexity (not code complexity).
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.
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?
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.
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 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.
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.
That depends on the scale. A couple jobs ago we had enough objects that an 80-bit key wouldn't have had a low enough collision rate (better models of computation for that domain include sqrt/cube-root ideas to account for information propagation in physical space). Sometimes you have to use more constrained devices so that your max effective constant-time word size (for the same computational cost -- not to quite be confused with the CPU's "native" word size, whatever that means in your circumstances) is 8, 16 or 32 bits (or, most recently at my last job, for _reasons_, 11 bits), making even quite small tables not quite O(1).
Many compsci researchers like the word-ram model of computation to avoid a bunch of extraneous log factors and to apply exactly the intuition you're describing, so that hashtables are actually O(1). That's not a bad habit. It introduces extra log factors in other places though, so I think it's a bit of a wash, and given that it doesn't model the actual register machines we use it feels a bit intellectually dishonest to me.
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.
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 operations 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.
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.
HN is such an experience nowadays. This has to be some form of LARP; insinuating the ineffectiveness of the inventor of the semaphore, 'not succeeded enough'.
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.
That's not median-of-medians, that's quickselect. Quickselect is useful and practical yes. Theoreticians don't like it because of the randomization (or non-worst-caseness)
> In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, most commonly quickselect…
That's pretty much what I posted: median-of-ninthers is an evolution of median-of-medians, that I use to pick a better pivot whenever the pivot supplied by median-of-3 turns out to be bad. There's also no randomisation, the implementation is completely deterministic, and depends exclusively on the input order.
Using it all the time would simply make quicksort/quickselect about twice as slow as it is now, but still faster than heapsort/heapselect. It's a better backstop algorithm than the common introsort/introselect.
And median-of-ninthers is faster, but median-of-medians is far from terrible, so calling it a galactic algorithm or completely useless in practice is far from the truth, IMO.
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.
There are other impractical aspects of TCS besides galactic algorithms, e.g. theoretically optimal data structures that are either too complex to be implemented or only achieve optimality in the limit (I guess the latter could be called "galactic data structures").
> 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.
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.
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.
> 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'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.
“breakthrough” is nothing more than an artifact of mathematicians not being able to properly specify the rules of their games in natural language… the theory of computer science has a culture that actively discourages running algorithms on a computer.
This is not an entirely faithful characterization. TCS and does make the distinction between galactic algorithms and what are called “feasible” algorithms (e.g., Karatsuba’s or Strassens’s algorithm), which yield a measurable speedup on practical inputs.
In my experience reading TCS papers, it is rarely made clear whether or not an algorithm is practical; generally one has to go pretty deep to figure that out
"I found the rot that develops inside applied mathematical theory when formalism becomes so detached from reality that a “breakthrough” is nothing more than an artifact of mathematicians not being able to properly specify the rules of their games in natural language."
it's like in my company, where some software developers get frustrated with an LLM that writes poor code. Understanding what you want—and providing the right examples and explanations—is crucial !
95 comments
[ 3.4 ms ] story [ 20.2 ms ] threadPS. I can have this view while simultaneously thinking that Ben is a badass.
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.
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.
The amount of information at high enough amounts scales with the volume in which it is stored.
Because of the need to be able to reach the cells that store information, the density of information is normally high in 2 directions an low in the 3rd direction.
This is why it is useful to distinguish between the density of information per area, which is determined by things like the size of a magnetic head or the resolution of a photolithographic process, and the density of information per volume, which is determined by the density of information per area and by some kind of layer thickness, which is usually determined by mechanical considerations, e.g. to ensure enough strength for a tape or a disk or an integrated circuit package.
Like I have said, at high enough amounts of information you reach an almost constant information density per volume, like in a rack full with HDDs or in a magnetic tape robotic library.
Ordinary memory is not a list. It's a flat space read in O(1).
In theory. In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
So if your entire data structure lives in cache and you repeatedly loop through it, it's going to be processed much more quickly than a bigger and more spread-out structure.
There's also paging, and alloc/dealloc to consider, and maybe garbage collection.
By the time you include all of that big-O estimates can become wildly misleading generalisations, unless your n is always >a million or so.
For small n it can be way off.
And in the general case, memory reads do depend on distance. Hence:
> In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
This is why we have the cache levels in the first place. And the hierarchy continues: L1, L2, RAM, block of spinning rust in the closet, "the cloud" somewhere... There is only so much storage you can fit close to core! More = physically bigger = physically further away.
Sure, within a level might feel like constant time. But that's because the optimal case for that level is slowed down to match the suboptimal cases. The step discontinuities in access time are caused by our inability to engineer a system to manage this tradeoff continuously, not a fundamental law.
If you build a computer with DRAM 10 cm away from the CPU and static RAM 50 cm away, access times for the static RAM will still be much lower than the DRAM.
Why don't we just build all RAM as static? Because it's more expensive per bit, it uses more energy, and it requires a great deal more silicon area.
First, find a sufficiently large base b so that no intermediate calculation exceeds b-1 (one pass over the matrices should do the trick). Then encode each row of the left matrix as a big value A_i = sum_k a_ik * b^k. Encode each column of the the right matrix as B_j = sum_k b_kj * b^(n-k). Compute A and B explicitly (takes O(n^2) integer operations).
Now you extract the answer one element at a time. A_i * B_j has a bunch of terms including sum_k a_ik * b_kj * b^n. All other terms have different powers of b. So do an integer division by b^(n-1), discard the remainder, then take the result mod b, and that gives (a*b)_ij, costing one integer multiplication and two divmod operations per output element. Problem solved. Can I publish in FOCS?
This is, of course, a wild cheat: even with OpenAI’s latest and greatest galactic integer multiplication algorithm, this is slower than the plain high school matrix multiplication algorithm on any real computer.
I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)
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.
Well, I want openAI to focus on these things instead, so it is not a totally unreasonable thing to advocate against their current focus
Yeah? Seems more like an ass.
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.
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.)
> 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.
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.
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!
https://github.com/CrocSwap/integer-mult-bounds
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 most trivial example of a baby step there is to have a lookup table for every kth element. That alone gets you below nlogn for any existing nlogn algorithm at the expense of storage complexity (not code complexity).
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?
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
> “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 is a superfluous remark because the article already said it. He criticizes theoretical computer science for doing it, not just OpenAI.
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.
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.
> 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
> 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.
Many compsci researchers like the word-ram model of computation to avoid a bunch of extraneous log factors and to apply exactly the intuition you're describing, so that hashtables are actually O(1). That's not a bad habit. It introduces extra log factors in other places though, so I think it's a bit of a wash, and given that it doesn't model the actual register machines we use it feels a bit intellectually dishonest to me.
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/Median_of_medians
That's pretty much what I posted: median-of-ninthers is an evolution of median-of-medians, that I use to pick a better pivot whenever the pivot supplied by median-of-3 turns out to be bad. There's also no randomisation, the implementation is completely deterministic, and depends exclusively on the input order.
Using it all the time would simply make quicksort/quickselect about twice as slow as it is now, but still faster than heapsort/heapselect. It's a better backstop algorithm than the common introsort/introselect.
And median-of-ninthers is faster, but median-of-medians is far from terrible, so calling it a galactic algorithm or completely useless in practice is far from the truth, IMO.
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.
Nobody really likes the definition of Big-O. It's been unmoored from actual computing performance ever since caches were invented...
> 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.
[0] https://news.ycombinator.com/item?id=49794330
Wake me up when someone has understood the proof.
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.
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.
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 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.
"I found the rot that develops inside applied mathematical theory when formalism becomes so detached from reality that a “breakthrough” is nothing more than an artifact of mathematicians not being able to properly specify the rules of their games in natural language."
it's like in my company, where some software developers get frustrated with an LLM that writes poor code. Understanding what you want—and providing the right examples and explanations—is crucial !