Hacker News Reader

Comment by p11p | Hacker News Reader

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.

View on HN

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.

Yes, misspoken. Anyway, not that I'm an expert here but my understanding is that at maximum density, information in a region 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 a Schwarzschild black hole). Is that incorrect?

The amount of information you are talking about is quite a bit lower than the amount I'm talking about. Big O is about limits, so if we're going to bring physical limitations into play to say there's some limit to density, you'd might as well go all the way. It's not limit as n -> 10^18; it's limit as n->infinity. You can't keep adding information and still get cubic scaling.

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.

For small n it can be way off.

For any big enough memory the speed of the memory reads will depend on address distance, at least due to the finite propagation speed of the data that is read.

Sequential reads from adjacent cells will be pipelined, so they can have a throughput that does not depend on the distance in address, but the latency to start another sequential read stream from a different address must depend on the address, for very big memories, e.g. of rack size, where the propagation from a corner of the rack to the other corner takes a long time in comparison with the memory clock.

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 access times for 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 would be asymptotically slower than the plain high school matrix multiplication algorithm in any remotely realistic model of a computer.

I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)

(The moral here is that exact math is quite powerful, and exact math in time sublinear in the number of bits of precision is a great way to steal some performance.)

Nice. I was trying to think of a linear time sorting algorithm using a similar cheat. Any ideas?

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

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.

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.

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.

> If you want that, you go to ESA, ALENEX, or VLDB/SIGMOD, or any of the other more applied venues featuring this work

Well, I want openAI to focus on these things instead, so it is not a totally unreasonable thing to advocate against their current focus

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.

>malice >shit on I don't think this is a productive or interesting way to discuss mathematics.

> I can have this view while simultaneously thinking that Ben is a badass

Yeah? Seems more like an ass.

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

Plenty of mathematics was practically useless for long periods of time, waiting for us to invent computers, cryptography, error correcting codes, etc.

It's extremely hard to know what mathematics may be useful in the future or not.

It's hard to know for certain, but that doesn't mean we should throw up our hands and say anything goes. We can still say that some things are more likely to be useful than others.

The idea that FFT's decomposition is non-optimal is surprising. What the new bound means is we basically were looking at the problem and its structure incorrectly, and therefore implicates other problems for which we have used recursion to get to our currently-best bounds. Almost no interesting math problems are just sitting there alone in their little corner. Getting a hint like that is a big deal.

Is it surprising though? If you assume constant time when it doesn't exist (in this case arbitrary precision arithmetic), it should be obvious that you will be able to devise algorithms that are faster than the commonly accepted best results.

If you can do arithmetic on arbitrarily large integers in constant time, you can sort lists in linear time.

It depends on what you're doing to the integers. You still cannot comparison-sort arbitrarily large integers in linear time.

Also, consider this: it would have been trivial to get a so-called "better bound" on FFT if such a "cheat" were what people allowed.

How can we say that without knowing the future?

Reply on news.ycombinator.com