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.
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.
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.
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.
There's also no randomisation, the implementation is completely deterministic, and depends exclusively on the input order.
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 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.
Dijkstra was an academic with no skin in the game.
If Dijkstra was so confident that he was right, he should have started a business and put his money where his mouth was. Hell, any True Believer of Dijkstra's could have done the same in the last 60 years. The fact that they haven't - or they've never succeeded enough for me to know of any - speaks volumes about their effectiveness.
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'.
Dijkstra's jeremiads were about promoting "formal methods" as the One True Method for software construction. Maybe there's a future for formal methods, but it wasn't ready in the past. No one was arguing about semaphores.
If not for Dijsktra you would not even exist to write the very sentence "Maybe there's a future for formal methods, but...".
What basic science does is open up new areas and new ideas. And you and I benefit from those foundations.
Dijkstra's proof methods derived from higher math sophistication than most programmers before, and today, have. Like, in one short essay he showed what invariants mean. He made formal theory accessible to mere non-pure-math mortals. You and I today know what invariants are. That's just one example.
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.
Yeah. Unfortunately a model that only knows how to use a language's standard library isn't that useful. I am not sure why they had a pull-through cache instead of just asking Microsoft (their biggest investor) for a local copy of NPM or something, but ... they did. I think people thought you couldn't route to the Internet through Aritfactory and were proven wrong by a clever bug-finding model. So it goes.
I don't think their safety measures were the best, but "just sink the cluster to the bottom of the ocean so nothing can get out" isn't a training methodology that results in a model that people will want to use.
I think we could have a little more sophistication than just a binary full|zero access. Hell, a lot of corporate IDS's are better than this (not a high bar).
I don’t think this is the right take. OpenAI employees are generally very competent compared to industry standard, and I have trouble believing they committed significant error in their sandbox design process.
I think what is happening is that the ability for frontier models to break out of sandboxes has exceeded the ability of average competent employees to build and maintain sandboxes. This doesn’t need to happen all the time. If the natural variation of agent executions cause agents to have ability to break out of sandbox 0.1% of the time, given how many agents OpenAI runs, this behavior happens eventually.
All sufficiently complex processes and software has bugs, but recently frontier models have become sufficiently advanced to exploit them.
My impression (HuggingFace incident) was they put some environment together in kubernetes like it was some B2B SaaS and tossed in an off-the-shelf package manager. And my thought there is, I know nothing about this package manager, but even if it's a pretty good package manager I would not expect such a product to be particularly hardened against being exploited to gain internet access. My other thought is if the package manager wasn't a convenient hole, they would probably have found something wrong with the kubernetes setup.
And then there was the Anthropic story where they just forgot to remove internet access.
Am I missing something here? The "sandbox" was an inability to make POST requests, only GET requests. This has to be the weakest and most insubstantial sandbox of all time.
So you’re saying that fucking up 0.1% of the time is acceptable, especially when it’s inevitable? I know it’s a stretch, but we’re in an industry where the concept of “five 9’s” is the gold standard.
I wonder how smoothly things would run on three 9’s. That definitely seems where we are going.
Let's do some roleplay. You're an employee at OpenAI evaluating a model in a sandbox and you and your colleagues are discussing the fact that while the sandbox doesn't allow for internet access, it actually kind of does allow for internet access in that it allows models to download whatever software packages they need through a package manager that OpenAI hosts internally. So to be clear, OpenAI hosts the package manager, but the software packages themselves are still out there, on the internet.
Do you think that this package manager could potentially be a problem? Do you think it might be worthwhile to host the software packages themselves on an internal, sandboxed network, just to be extra certain? Or would you dismiss this as a needless precaution?
No, it is a shocking level of incompetence given the conveyed seriousness of the work by these labs.
So yes, models are getting better. Ask yourself: if you know that to be true, would you act the same way that the teams did in the public post mortems?
I have encountered instances where Claude 4.6 on Bedrock appeared to be more personable than the Claude 4.6 on Claude web. I think the system prompt plays a role in making it more "customer service" like in certain situations.
> 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