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.
A decade is nothing. If issues will be worked through a decade from now, that means the best time to think about opportunities/coonsequences related to that is now.
Yeah, I see people pooh-poohing the idea of humanoid robots being useful this decade, saying it will take at least 20 years. Oh yeah? Instead of 5 years to render all human labor obsolete, it will take 20? The magnitude of that change is so large that the implications of it happening anytime in our lifetimes are too big to ignore.
The important thing is that this is not going to be perpetually 20 years in the future like fusion. This is something that will happen.
> The important thing is that this is not going to be perpetually 20 years in the future like fusion. This is something that will happen.
Meanwhile, in 1950: "the important thing is that fusion is not going to be perpetually 20 years in the future like the eradication of all disease [there was a time in the 40s and 50s where people, a bit over-excited about then-new antibiotics and chemotherapy, often did believe this]. This is something that _will happen."
> Oh yeah? Instead of 5 years to render all human labor obsolete, it will take 20? The magnitude of that change is so large that the implications of it happening anytime in our lifetimes are too big to ignore.
While true, I would suggest two things:
First, that nobody actually knows how long it will take to make fully-general AI to drive robots, humanoid or otherwise. Look how long self-driving cars have taken, and that they're still geo-fenced.
Second, that it doesn't take AI for the robots themselves to have 90% of this impact. All those jokes about AI meaning "Actually Indians"? Well, the same robots controlled not by artificial intelligence but by remote control from cheap 3rd world labourers who charge $5/day, will make current arguments about the effect of immigration on unemployment look laughably naïve. Likewise, unfortunately, crime, because one thing we can guarantee is that someone's going to share their password or access token and some rich person's cheap robot servant will become Mr. Stabby the unknown assassin.
You do. And so does your non-technical mother (or a friend of your mother).
The impact of the iPhone and its competitors is felt everywhere, it diffused into every domain of people's lives. Think: the whole of social media was pretty much enabled by smartphones.
Or a more pedestrian, random example: every day I go to the office, I see endless store managers, restaurant managers, etc. walking around their store, making photos to upload to HQ. But this is merely a symptom - the actual consequence is the change in busines structure. It's because smartphones make this easy, that it makes franchise and subcontracted businesses more viable, because it's easier for the HQ to micromanage more semi-independent subordinates.
There are many, many more examples like this everywhere you look. Which is why I'm inclined to agree with Karpathy: computers, iPhones, LLMs, are all the same thing - it's just the more notable manifestations of how we've been staying on 2% growth exponential curve for many hundreds of years now, and why we'll continue to stay on this curve.
But the caveat is: that curve is getting steep enough that the world is starting to transform faster than we can handle.
The iPhone came out less than 20 years ago, and now I:
• Don't get out my debit card while shopping.
• Don't get lost exploring a new city.
• Have zero-cost video calls with anyone I want.
• Use most spare moments of my time — walking to the shops, or on public transport, or while hiking in the countryside — learning something new. When I'm not too damp for the capacitive touch screen, that can be interactive lessons, not just passive; but even for the passive consumption, mobile internet beats pre-loaded content on an MP3 player.
• Have a real-time augmented-reality translator, for the German I've not yet learned while living in Berlin, and all the other languages I don't (or barely) know while travelling outside the country.
You take out your phone though. How is taking your phone out of your pocket, logging in, and tapping it on a terminal significantly different from pulling a credit card or cash from your pocket and tapping the terminal or handing it to the checker?
• Don't get lost exploring a new city.
You're young, I guess. We had GPS in cars well before iPhone. GPS navigation in cars was taking off mid-90s to mid-2000s. I had a Garmin in 2002.
• Have zero-cost video calls with anyone I want.
I was doing that on my laptop and desktop before iPhone. Heck, I was doing free video conferencing with European friends in 1995.
• Use most spare moments of my time
I did much of this filling in empty times on my laptops years before iPhone but you are right, not as much of it as with smartphones. Cramming my day full of even more noise, however, rather than having more breaks from it, feels like devolution to me.
• Have a real-time augmented-reality translator
This is an improvement over pocket electronic translators I was using in Japan in the early 2000s, but really the improvements are mostly in fidelity and usability, not in function.
Don't get me wrong, smartphones changed a lot, but it seems like you're eliding at least a decade of pre-iphone advancements here and focusing on when these tasks became easy and in everyone's hands, rather than when the tasks actually became possible and were in reasonably widespread use. You're not a youngster like many here, so I can't attribute that to naivete and that leaves me thinking haste was at work here. Happy to hear back why I'm wrong and willing to change my mind on any of these.
> How is taking your phone out of your pocket, logging in, and tapping it on a terminal significantly different from pulling a credit card or cash from your pocket and tapping the terminal or handing it to the checker?
Biometric ID to make the payment. I don't so much "log in" as "touch the fingerprint scanner built into the button that switches the screen on". Though if I cared to wear it, I do also have an Apple Watch and would therefore not even need to take anything out of my pocket.
> You're young, I guess. We had GPS in cars well before iPhone. GPS navigation in cars was taking off mid-90s to mid-2000s. I had a Garmin in 2002.
Just about to turn 42. I saw GPS in use only a little later than that, 2005 I think. But:
1) dedicated GPS was never in everyone's pocket until smartphones became normalised; and even then, location precision was mediocre until assisted GPS got phased in (IIRC the first consumer phone with A-GPS was about a year before the iPhone?)
2) the maps were incredibly bad; my experience in 2005 included it thinking we were doing 70 miles an hour through a field because the main road we were on was newer than the device's map.
3) Phone map apps also include traffic alerts, public transport info including live updates for delays, altitude data (useful for cyclists), ratings and hours for seemingly most of the cafes/restaurants/other attractions, and simply has a lot more detail because it can afford to (e.g. many of the public toilets).
> I was doing that on my laptop and desktop before iPhone. Heck, I was doing free video conferencing with European friends in 1995.
Critical point: "with anyone I want". Almost every independently functioning person in Europe, has a smartphone, and can be contacted without waiting for them to sit down at a desk terminal connected to a fixed line internet connection that was currently switched on.
Back in 1995, most people didn't have the internet at all, so no possibility at all to call them over the internet; those who did have it were either academics (yay JANET), had a relatively expensive wired ISDN line, or were on dialup (charged by the minute and had just about enough bandwidth for 3fps greyscale at 160x120 or so if the compression was what I think it was), and while mobile phones did exist back then, they were (1) unaffordable unless you were a yuppie, (2) didn't have cameras, (3) even worse bandwidth than dialup because 2G.
> This is an improvement over pocket electronic translators I was using in Japan in the early 2000s, but really the improvements are mostly in fidelity and usability, not in function.
I count "point camera at poster, see poster modified with translations overlaid over all text" as very much a change of function.
I mean, I don't need to translate Chinese, Japanese, Korean, or Arabic, but sometimes they come up in films and I get curious, but I can't type any of those alphabets in the first place so the only way to translate it is with something like Google Translate (and its predecessor Word Lens) that does it all as a video stream.
> focusing on when these tasks became easy and in everyone's hands, rather than when the tasks actually became possible and were in reasonably widespread use.
For much of this, that's the point. As the quote goes, "The future's already here, it's just not evenly distributed". I assumed it would be clear video calls can only be had with other people that also have video call equipment.
Or forward looking, look at how there are cars with no-steering-wheel-needed (even if Waymo has not actually removed them) full-self-drive, but they're geofenced. It's there, it's not everywhere.
With AI and human labour? Well, that's a two-part thing, the hardware and the software.
Software? The software running these robots can (just about) fold laundry, or tidy up litter and dishes — you know, all the things that people keep sarcastically listing to dismiss AI, saying "wake me up when they can XYZ": https://www.youtube.com/@figureai/videos
It's just… these robots are expensive, kinda slow, and the software gives me the same vibes I got from AI Dungeon (I think I saw it shortly after they changed away from GPT-2?), so I ask the same question of those today as I asked myself of a 3D printer in 2015, of an iPhone in 2010, of a multi-language electronic travel dictionary in 2009, of a dedicated GPS unit in 2005, of a laptop in 2002: can I really justify spending that much money on this thing? And my answer is the same: no.
I can't run the fanciest AI models on any of my devices, they won't fit, I'd have to buy a much beefier machine. There's a whole bunch of things that the SOTA AI models themselves can't do yet, but which can be done by tools that AI do know how to use, but I can't run all of those tools either. Any tool that gets invented in the next 20 years (or indeed ever), if it's documented at all in any language current LLMs can follow, those LLMs will be able to use them.
Now don't get me wrong, I'm not holding my breath or saying this will be soon. I've opined before that the minimum gap between "a level-5 self driving car" and "a humanoid robot that can get into any old car and drive it equally well" is 5-10 years just because of the smaller form factor having less room for compute and battery. Also, it seems obvious that "all human labour" is a harder problem than "can drive". If (if!) it is necessary to have humanoid robots in order to render all human labor obsolete, then I would be surprised if it takes any less than 15 years from today, but could be more — easily more, and by an arbitrarily large degree. I don't think humanoid robots are necessary for this, which reduces my lower bound, but at the same time it is just a lower bound.
I don’t understand how this works. I know someone who founded successful startup based on art-painting robots. But why will anyone buy such art not attached to fame? Unlike bitcoin, the supply of such art is not limited. It’s still infinitely reproducible through the robot.
> 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