Hacker News Reader

Comment by skybrian | Hacker News Reader

If algorithmic theorists don't care about practical performance then why should we care about what they're doing? It's just a strange game they're playing, of no interest to anyone else.

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.

View on HN

You care because Pierre de Fermat 16th century work on modular arithmetic was of “no intest to anyone else” except other theorists but it got to shine in the twentienth century in modern cryptography.

Doing theory is what gives you a chance to push the envelope to places you can’t even imagine when you’re knee deep in real world problems. And proving something is possible (if impractical) gives an incentive to find a better algorithm and may attract others.

For example see the first graph here: http://klotza.blogspot.com/2016/06/the-fall-of-twin-prime-ga...

No, I don’t care. Until there is a real, practical result, I don’t care. There are plenty of examples of math discovered in service of solving a problem. There is nothing that says math has to be purely abstract first.

You can't imagine how that severely limits the potential size of the discovery space shackling it to present day problems?

I think the poster is distinguishing between currently practical and ever practical. Galactic algorithms can never be realized.

The constants can be made lower. If we didn't know about the galactic algorithm beforehand, we couldn't begin to do that.

Because clearly we’d have invented GPS if we had asked ourselves “how do I create a global positioning system with centimeter accuracy”?

That is how we invented GPS...

And without relativity theory positioning error would be measured in kilometers.

I've always wondered - if special and general relativity weren't known, could the GPS engineers have just measured the error and empirically accounted for it? I don't know relativity or GPS or engineering well enough to answer.

It's possible, but it seems more likely that the first tests would have shown "weird timing errors we couldnt diagnose" and then the project never got a follow up.

For something so militarily useful? When the Soviet Union was still seen as a threat to the US? When it was already so expensive anyway? I guess it's possible, but it's hard to believe they'd just give up like that.

The problem with "it's hard to believe" is that this is an area where I'm not even sure how to effectively estimate the counterposition, I've seen things that I thought were interesting get cancelled or have no follow up all the time, and it makes sense, no idea if it will matter, or even work, and even if it does, how much will it cost to realise any value?

Who knows how often really impactful tech is gated behind some non-obvious thing which we never follow up on.

I mean Douglas Engelbart basically bet his entire career behind the Mother of All Demos[0], if it had flopped, modern computing as we know it would be fundamentally different, same with Hiroo Kinoshita and Extreme Ultraviolet Lithography[1][2], we just would have had Moore's law falling off a cliff.

-[0]: [The Mother of All Demos, presented by Douglas Engelbart (1968)](https://www.youtube.com/watch?v=yJDv-zdhzMY)

-[1]: https://spie.org/news/photonics-focus/mayjune-2023/developin...

-[2]: [The Closest Thing We Have to Alien Technology by Veritasium](https://www.youtube.com/watch?v=MiUHjLxm3V0)

Yeah, absolutely. You'd be surprised how much high-precision engineering absolutely relies on "this but you have to mill a tiny amount off the end because if you do the maths it comes out ever so slightly too big, and then adjust on test".

Yes, the clock slippage is a constant factor, entirely predictable. If made public it would probably have catalyzed the discovery of special relativity soon afterwards, but then people would’ve been super confused because its predictions still wouldn’t match the observations and indeed would widen the discrepancy rather than narrowing it!

A modern-time retrograde of Mercury.

Of course, the good-old-fashioned retrograde of Mercury would still be a real puzzler in that timeline, too.

Relativity is required to explain the time dilation, but it's not needed to notice that the GPS clocks run 40µs too fast. It wouldn't take too long for them to measure enough data to create an empirical skew-versus-altitude table, which should then be enough for them to correct the time skew, even without understanding what was going on.

I think this is a difficult counterfactual to assess, we didn’t develop clock accurate enough to notice the time dilation until 50 plus years after the theory of relativity was published.

Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere? Maybe they would mothball the GPS project for not working before figuring it out? It’s hard to know, 50 years in an alternate timeline allows for a lot of domino effect

> Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere?

They probably would just assume that it's a bug at first, since "our clock is slightly broken" is far more likely than "we've discovered some cool new physics". But I don't think that that would be an issue here, since even if they thought it was a bug, they'd still try to work around it.

> Maybe they would mothball the GPS project for not working before figuring it out?

I doubt it, since if you think about all the possible issues after sending a complex untested satellite to space, a 40μs clock discrepancy is fairly minor.

doesn't it use special relativity or some modern physics?

If only we could figure out how to get rid of the pesky ionosphere....

... at least in a way less intrusive than https://www.sciencedirect.com/science/article/pii/0021916964...

Ironic username as I doubt we'd get to the stars with your philosophy.

How far are you willing to go? In your radical pragmatism, are you an intuitionist, or even a finitist? Oh wait, these are pure math topics that you do not care a about!

And that's fine, caring about everything is exhausting, someone has to solve real world problem. But dismissing a result since it's not practical is not fine

Why not.

Dudeee how far up your hind do you need to be to nit even appreciate the groundwork being laid out?

Like imagine Einstein without access to geometry work. You had others point you to number theory. What about Boole's algebra.

There is a pretty big list of seemingly useless pure math things suddenly finding a very practical use. Sometimes quite a bit later too. And we have no way of knowing beforehand.

And it's fine to not want to do such work yourself. But to dismiss it is, well, not very thoughtful.

Imagine Newton without access to calculus. Poincaré and the three-body problem without topology. Gibbs and Heaviside without vector calculus. Or Fourier without, well, Fourier analysis.

The lack of mathematical tools posed no special challenge for any of them. They invented the math they needed to do their work.

You are presenting a false alternative history, where they would not be capable of making great insights without the math coming first. But the causality is often the other way around.

And I don't care about your opinion. Checkmate: two conflicting, essentially valueless, opinions.

Not everyone needs to care about everything and there is reason to say that a result like this one from openai is quite sterile and possibly damaging to the socio-cultural dynamic of the field.

Considering this line:

" In 1973, Jacques Morgenstern proved that you couldn’t get a Fourier transform faster than ½ n log n if you required that complex coefficients used in the computation had bounded magnitude"

I highly doubt this is going to somehow inspire people to make faster algorithms than the mathematical bound...

I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.

Does the apply to representation of complex numbers, which is not uncountably infinite and represented by floats?

Yes. It applies to "linear algorithms", which are basically functions of the form

  fun f(x1, x2, x3, ...):
    t1 = 3*x1 + 2*x2
    t2 = 4*t1 + 5*x3
    ...
    return (some subset of t vars)

where each ti is a linear combination of previous t vars, inputs x vars, or constants.

The cost model is just the number of additions performed.

That's absolutely fascinating. I need to read up on this -- thanks for sharing!

>I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.

Most people getting funding for pure maths probably just lie and/or stretch the truth that it tangentially has some relation to or possible benefit to practical things like cryptography. It doesn't need to actually be true. It just needs to feel true enough.

It's like all the robotics works that obviously might be applicable to Search and Rescue and help firemen fight fires.

The algorithm from OpenAI works also in prime-order finite fields. Such FFTs are used all over the place in cryptography. So clearly their result is not useless and works in a realistic computational model

Huh, I wasn't aware; I haven't looked into the construction, I was just taking the blog posts claims for granted. Does it extend to all finite fields, that'd be super cool if so.

I find that an extremely inefficient way of thinking. Spending time on problems on the minuscule off chance that a few centuries later they will be useful whereas you could be spending time right now on problems you know for a fact are useful is a weird trade off to make.

OK, here's a different tack, then.

It is almost completely impossible, and therefore a waste of time, to attempt to gatekeep what other people wish to spend their time and energy on.

There's no single hand holding the pursestrings of research. There's no single path to implementation of theory IRL.

Talking about what "should" be studied is arrogant at best.

Yeah but we are not talking about what should be studied, but rather what should be funded

Both opinions are being voiced here (albeit maybe some are just bad at wording things). And gatekeeping what others should do with their money is stupid. And coincidentally, actually communist, or oligarchist of some flavor.

Spending time commenting on HN is even less likely to yield useful mathematical results in a few centuries, but here you are.

I disagree with your implication; modular arithmetic is much more obviously useful, and would have been back then too (supposing hypothetically you explained the notion of a galactic algorithm to Fermat), because it's an abstract mathematical structure and thus likely to recur in new scenarios.

I think you are free not to care about what they are doing. It turns out that big O notation has some useful properties, and in particular it is a useful definition as it allows you to define complexity classes which are a very useful tool for analyzing algorithms in general.

Much of our 'practical' understanding of algorithms also in part came from theoretical advances.

That’s sloppy reasoning. There might be notations that allow for classifying complexity classes that don’t suffer this problem.

That may well be the case, in theory.

You're free to propose one and see if it catches on

There might not be, how is your reasoning any less “sloppy”?

your reasoning is sloppy. so confidently incorrect throughout this thread!

The argument in the article isn’t about whether big O notation is useful it’s about whether the n in any particular big O is relevant. In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.

The complex FFT is a generalization of the n-bit integer multiplication algorithm, not the other way around. No complex-number operations are required for the integer case.

> In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.

Well that's certainly not the claim. Think about it, that would mean the whole thing is trivially O(1), so why would they be bothering with the rest?

You've missed part in the analysis, or I believe added an assumption they're not making (the constant-time-multiply one, specifically).

This all _is_ almost certainly impractical, but it's for the usual reason of it only being faster for numbers nobody could ever care about. It's theoretically _quite_ interesting though, because hey...what _is_ the fastest you can actually multiply numbers if it's not O(n lg n) as many ~assumed.

> If algorithmic theorists don't care about practical performance then why should we care about what they're doing? It's just a strange game they're playing, of no interest to anyone else.

You don't need to care. But every so often breakthroughs in theory can be turned into breakthroughs in practice.

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

There's plenty of replacements.

Btw, we already have the optimal (in big-O terms) algorithm for every NP hard problem. We just don't know whether it runs in polynomial time or takes longer. And, yes, that algorithm called Levin's Universal Search is a galactic algorithm. Simplifying a lot, Levin's Universal Search does some clever interleaving to essentially try all possible algorithms in sort-of parallel.

Lo and behold, even the theorists you complain about don't see that 'loophole' as a solution, declare victory and go home. They still keep researching.

If Big-O lets you run every possible algorithm in "parallel" while still being in some sense "optimal," that seems like yet another exploit?

As I read it, that was sort of their point: if the theorists were blindly focused on Big O complexity, they could 'cheat' by invoking the universal search algorithm as a good-enough solution to a huge class of problems; but they don't, because they're not mindlessly playing a game where Big O complexity is all that matters.

Yes, exactly. I'm afraid I didn't make myself very clear. Thanks for explaining it better than I did.

The reason universal search doesn't solve big O complexity is that nobody knows the big O complexity of universal search. You want to know the complexity of SAT.

"Ok, here's an optimal SAT algorithm (universal search)".

"Nice, but what is the big O complexity of universal search for SAT?".

"Nobody knows".

You're no better off than before if you wanted an answer like "exponential". On the other hand a provably sub-exponential SAT algorithm would be a huge theoretical breakthrough even if "galactic". Same for a proof that P=NP where the exponent in the P-time SAT algorithm was the 5000th busy beaver number, or whatever.

Agreed.

Also empirically, pretty much any provably polynomial algorithm we have found for anything has fairly tame exponents. That's a big part of why 'polynomial' works as a short-hand for 'tractable' that also has nice theoretical properties.

Btw, I don't know whether the tame exponents are in some sense natural, or whether they are a product of how humans find and design algorithms. Perhaps AI will change that.

Yeah I seem to remember that the earliest known algorithm (Schoof's algorithm) for counting points on an elliptic curve over a characteristic-p field was O(n^8) where n is the bit length of p. But, much more efficient algorithms are known now. I don't know of anything with a higher exponent than 8. The time hierarchy theorem says higher exponents let you solve more problems, but idk if there are natural examples of such problems.

Here's a cool old thread about this topic.

https://cstheory.stackexchange.com/questions/6660/polynomial...

It's not an exploit, it's a gap in our understanding of the algorithms. We know it's optimal, but we don't know the Big-O complexity.

Well, it's an 'exploit' in the sense that normally we assume that the constant factors are modest enough so that O(n) can be reliant upon to be faster than O(2^n) or even than O(n^2) in practice.

It's not a constant factor, that's the misunderstanding. It's an unknown factor.

They do care. They also care about partial results. As of last week, we thought we knew the best possible algorithm. We now know that there's a galactic algorithm that's an asymptotic improvement. The question then becomes "Is there a non-galactic algoritm that does the same, or is any such algorithm necessarily galactic?"

The problem is that proving an algorithm is necessarily galactic is incredibly hard. If you knew how to do this, you would become one of the most celebrated complexity theorists of the age. Stanford would be calling.

Theory is theoretical, that's what the word theoretical means. Set theorists deal with numbers and collections that are literally infinite and nobody complains. Complexity theory is much more down-to-earth since the numbers are finite. That's about as good as it gets. If you want practical, study engineering.

Reply on news.ycombinator.com