YHK - yet another hacker news clone

It seems like rather than coming up with more "galactic" algorithms, a more useful thing to do might be to come up with a replacement for big-O that's not so exploitable, and to convince theoreticians to play that game instead.

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.

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.

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.

This is a common thing in complexity, and I think even the abstract says it is talking about “length n” and not “magnitude n”

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.

I don't think that's an accurate summary of the article you linked. The Lean proof solved the exact problem it was supposed to, it just had minor discrepancies from the writeup of the proof (on the level of saying a theorem requires m+4 derivatives when it actually requires m+5 derivatives). Obviously a problem but not really a bombshell.

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.

> 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.

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.

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.

[0] https://news.ycombinator.com/item?id=49794330

A good one though. A theoretical computer science which researchs "algorithms" which are impossible to run on a real computer has gone astray.

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.

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.