Rendered at 14:55:35 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
meffmadd 15 minutes ago [-]
Off-topic but is there a project/"template" to host these Auto Research projects?
krackers 13 hours ago [-]
Is there any good writeup yet of intuitively where the speedup comes from? E.g. with fast fourier transform you can see that there's a lot of symmetry & recomputation in the Vandermonde matrix, so that's where the speed up comes from.
AnotherGoodName 12 hours ago [-]
The site is taking forever to load but complexity theory doesn't really have the hard walls at things like O(nlogn) that people seem to think.
You can always always tradeoff time vs space. It's actually a fundamental part of complexity theory called Blums speedup theorem by the guy who invented complexity theory no less.
As an example you give me an nlogn solution and i take a portion of the inner loop, put it in a lookup table (who cares if the lookup table is 2^n in size, that's not what we're measuring here since we're specifically measuring time not space) and suddenly i have something better than nlogn since that lookup table is O(1).
That's not to say there's some merit to all of this. It's just that people shouldn't be as astonished by these results as they are. It's complexity theory. There's literally no such thing as a hard wall where something is nlogn in time and can't get lower. It can always get lower. But you need both the time and space complexities together to reason about this.
openasocket 27 minutes ago [-]
It’s been a while since I studied complexity theory, but is that what Blums speed up theorem says? A quick google search suggests it states that there exist computable functions where there is no optimal program that computes it.
Like, there exist problems that have a lower bound of n time where algorithms can get arbitrarily close to O(n) complexity but there is no program that actually reaches it (there is one that runs in time O(n^{1.1}), one that runs in O(n^{1.01}), etc).
But that doesn’t mean that there aren’t hard walls, it just means there are hard walls where every program’s runtime is > that wall, rather than >= that wall. But maybe I’m misunderstanding, or there are some corollaries I’m missing?
As an aside, as someone who studied more on the pure math side, Blums speed up theorem is rather intuitive. It looks like there might be a relatively elegant proof using topology. Blums speed up theorem is basically just a statement that the set of programs that implement a particular computable function doesn’t satisfy the greatest lower bound property. This is also the case for, for example, the set of rational numbers: there exist subsets of the rational numbers with a lower bound but not a greatest lower bound (like the set of all positive rational numbers q where q^2 >= 2). I’m hand waving, but I think in that same vein you can show that the set of programs under the topology of ordering by runtime is completely disconnected.
kevinwang 1 hours ago [-]
> There's literally no such thing as a hard wall where something is nlogn in time and can't get lower.
Isn't this an ironic example to use, since one of the only lower bounds we have actually found is nlogn for comparison-based sorting?
And anyways, this point seems too strong: the fact that TCS people believe NP != P is another example that we believe a lower bound exists, no? (And relatedly, the large portion of TCS that is dedicated to trying to figure out how to lower-bound anything, while admittedly not so successful yet, shows that researchers believe lower bounds exist. I mean, any complexity class non-equality hypothesis is an example of this, no?)
tgv 8 hours ago [-]
> You can always always tradeoff time vs space
Not always, isn't it? The theorem says that there exists a function that can be sped up, but not that every function can be. A trivial counter example would be the identity function on a TM. It's simply a HALT/ACCEPT. There's no way to reduce that.
The space/time trade-off is also not infinitely flexible, since it takes time to fill space. And lookup tables have to be constructed at run-time, or they'll be of finite size, and hence only a constant speed-up. Perhaps you were thinking of that theorem, the linear as wikipedia calls it? https://en.wikipedia.org/wiki/Linear_speedup_theorem
hansvm 16 minutes ago [-]
That particular lookup table would be O(n), and it wouldn't support unbounded inputs.
jkhdigital 3 hours ago [-]
No, lookup tables aren’t magic. The lookup table is part of the program and the execution time includes reading the program itself. A table of size 2^n takes O(2^n) to read into memory.
david-gpu 2 hours ago [-]
You can read the table on demand. If you are only processing n elements with an algorithm that is very roughly nlogn, you would not be reading all 2^n entries of the lookup table.
_alternator_ 45 minutes ago [-]
Yes, but writing down the address in the lookup table takes log(2^n)=n bits, so the claim of an O(1) lower bound is simply wrong.
erichocean 24 minutes ago [-]
I do not encourage you to look at the diagonalization argument, it has similarly uncomputable elements (that take "longer than infinite" time because they are unconstructable).
crest 3 hours ago [-]
Than you modelled it incorrectly or n is small. A large lookup table is not O(1) in the real world as anyone who compares the access time of a register file, an L1 cache, and HBM3 (or DDR5) memory would realise. Even in a world of spherical cows in a vacuum lookup latency increases at least linearly with the radius of spherical volume the signal has to pass through.
david-gpu 2 hours ago [-]
However non-uniform your data access latencies are, algorithmic analysis treats all of them as O(1) as an axiom.
If you don't like that convention, you are free to use your own, but it is going to confuse people who use the standard convention. And the convention makes a lot of sense when you stop and think about the problem that people are trying to solve.
cma 12 hours ago [-]
Wouldn't it take an infinite lookup table to do this satisfying any two integers and still get an order-complexity speedup? The integers can be any size. You can't specify an arbitrarily variable sized lookup table in the normal formulation of these problems without computing the lookup table as part of the computation.
sroussey 10 hours ago [-]
You seem to under the impression that we don’t currently use lookup tables for multiplication.
But your right in that we don’t have a huge LUT as it’s not worth it.
Small one in the ALU though, for partial products to add can be worth the additional wire length.
cma 3 hours ago [-]
I don't believe that changes asymptotic worst case order complexity for multiplication of arbitrary sized integers on its own, naively applied. That's not the same as saying it doesn't provide any speedup to them.
AnotherGoodName 12 hours ago [-]
Never infinite if you have bounds on integer size. For n bits of input it's always possible to have a 2^n space complexity lookup table that's O(1) speed since 2^n covers all possibilities of n bits.
You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.
vlovich123 11 hours ago [-]
I think the thing non-mathematicians and non-CS people who only know complexity theory vaguely need to remember is that complexity theory has nothing to do with reality.
A 2^64bits lookup table only has O(1) lookup if you ignore the impossibility of creating a machine that has 2 exabytes of storage where all those bytes have the same access time. Or you'd have to redefine O(1) to be “at most the worst case”. But strictly speaking from the mathematical definition it’s O(1). Which is why no one in practical engineering takes most complexity results seriously as the entire field maps to practice poorly precisely for these reasons (all our machines use fixed integer math and have limited tape storage)
bluecalm 11 hours ago [-]
The whole point of this problem is that there are no bounds on integer size.
The whole point of complexity theory is that there are no bounds on input size.
AnotherGoodName 10 hours ago [-]
Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite. Thats the end state of Blums speedup theorem in either direction and it doesn’t limit to any bounds. I just stating a limited of bounds above for the sake of giving understanding. Complexity theory doesn’t care that 2^n space complexity doesn’t work when n is infinite anymore than it cares that nlogn also doesn’t work when n is infinite. It’s not the point.
kadoban 6 hours ago [-]
> Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite.
That's just incorrect. Are you assuming the table starts pre-filled, and has O(1) lookup? Nobody is using a model like that for this problem.
2^n space complexity doesn't automatically mean you get to fill that space with 2^n chosen computed values for free.
There's models with "oracle"s for various sub-problems and such (that's essentially what you're describing as the ability you're baking in to your model of computation, it can look up the answer to any multiplication for free), but that's not an interesting model for this problem.
If you do that you're just asking "hey, how long does it take to multiply two numbers if multiplying two numbers is free". Boring question, and not the one anyone else is asking.
testaccount28 10 hours ago [-]
nah dude. i'll allow any finite size lookup table, but not an infinite one.
adgjlsfhk1 9 hours ago [-]
no it doesn't. making the table takes O(2^n) time
luc4 7 hours ago [-]
Congrats, you just solved P=NP.
akoboldfrying 5 hours ago [-]
> There's literally no such thing as a hard wall where something is nlogn in time and can't get lower
I guess you're saying that this holds in "realistic" computational models? Sorting in the decision tree model is famously \Omega(n log n)-time.
BrtByte 9 hours ago [-]
[dead]
32 minutes ago [-]
ssivark 9 hours ago [-]
Ben Recht has a nice blog post about how these results are basically reward hacking the TCS formalization by assuming atomic operations for exact complex arithmetic, instead of costs scaling with the size/precision of the number: https://www.argmin.net/p/faster-fourier-transforms
number multiplication is basically convolution and closely tied with FFTs, so I wouldn't personally be surprised even if a lot of the "FFT's work" could somehow be stuffed into exact arithmetic operations, and the remaining costs just track the packing and unpacking from that representation. It's just an exploit of the book-keeping.
That's ignoring the other complaints about this being a galactic algorithm.
ComplexSystems 8 hours ago [-]
This is a very loaded blog post. A unit-cost RAM is a fairly standard model of computation when working with algorithms. When we say that comparison sorting of strings takes O(n log n) time, for instance, we are also implicitly assuming a unit cost for comparing two strings. In real life, comparing two strings scales linearly with string length. Maybe that's silly, but it's par for the course. The original FFT is also assuming unit cost multiplication when we say it is O(n log n) time - we mean O(n log n) multiplies.
Similarly, yes, it's a galactic algorithm, but these things are still viewed as meaningful. The fact that it is even possible at all with a unit cost RAM asymptotically is an incredible result that nobody expected.
ssivark 6 hours ago [-]
The string comparison model is useful in the regime where string lengths are much shorter than list lengths and can be bounded by a constant. It would be a horribly broken (i.e. unrepresentative) model if you were constructing intermediate strings whose lengths could grow arbitrarily and become much longer than list lengths.
One can of course make a puzzle out of anything, but it behooves asking what situation is being modelled by that problem.
And yes, this criticism might apply more broadly to TCS rather than just this specific artifact from OpenAI. It's reward hacking regardless of whether humans do it or LLMs.
ttoinou 8 hours ago [-]
Have we settled on a really good universal approximation model of memory+computation or is this a hard topic to solve in itself ?
adgjlsfhk1 9 hours ago [-]
this blog post is notably wrong on several counts. Firstly, the <nlogn multiplication is using a traditional multi tape Turing machine model which doesn't have the same tricks the dft result uses (and the dft result can similarly be reformulated at the expense of a less readable paper.
Also the 10^-13 isn't an optimized number. Current results are up about 10 orders of magnitude (10^-3) and show little sign of stopping. it's seems entirely plausible that we might get to nsqrt(log(n)) (with a likely still astronomical constant)
throwaway198846 6 hours ago [-]
Is that a natural barrier for the current method or we could also have n(log n)^epsilon ?
krackers 9 hours ago [-]
>instead of costs scaling with the size/precision of the number
But isn't the assumption that arithmetic is "atomic" standard in TCS? Costs do scale with the bit length, presumably they aren't assuming that addition is "constant time" with respect to # of bits (which would defeat the whole point of the exercise).
Maybe I'm missing something, but none of the things mentioned in that blogpost seem particularly "surprising" to me, most of it focuses on the fact that computational models used in TCS don't align with the real-world model of computers, but that seems like something you learn in day 1 of algorithm analysis? If you want something closer to real-world you'd use word ram model.
pfdietz 59 minutes ago [-]
The model I like is assuming the numbers you manipulate in O(1) time are bounded by some polynomial in the size of the input. Or, O(log n) bits. This seems reasonable, as just addressing a size n input uses addresses of O(log n) bits.
One can do some interesting things in this model, such as the van Emde Boas data structure for O(log log n) integer set queries, and tricks where O(log n) size subproblems are converted to lookup tables.
ssivark 5 hours ago [-]
That's passable model assumption if your algorithm didn't create intermediate numbers/strings of arbitrarily growing length. Otherwise the thing that you're considering a constant is not actually bounded.
Whether it's an oversight in just this work, or TCS more broadly, I do not know. But it's a fundamental point nonetheless.
I don't understand anything. Are the contributions in Lean?
Did they start with OpenAI's Lean proof and continue work on that?
Does the Lean proof grow significantly, or are they also trying to keep the Lean proof short-ish?
Tycho 5 hours ago [-]
This thread represents HN at its best. What a time to be alive!
namjh 8 hours ago [-]
No offense to the participants, but TBH I believe this is exactly the moment what Terrence Tao was concerning on "vibemathing". OpenAI breaking the O(N log N) barrier could be a meaningful event and surprise mathematicians and we have valuable information that it was not a lower bound indeed. I'm afraid that in this autoresearch campaign people are focusing only on lowering numbers, while having insights that humans can learn.
erichocean 22 minutes ago [-]
What he is calling "vibemathing" is actually just engineering.
Engineers don't have to know why something worked in particular in order to use it, they just do.
Science later tries to figure that out.
Both are valuable, but the idea that science must be "first" is, at best, unsupported by the evidence.
You can always always tradeoff time vs space. It's actually a fundamental part of complexity theory called Blums speedup theorem by the guy who invented complexity theory no less.
As an example you give me an nlogn solution and i take a portion of the inner loop, put it in a lookup table (who cares if the lookup table is 2^n in size, that's not what we're measuring here since we're specifically measuring time not space) and suddenly i have something better than nlogn since that lookup table is O(1).
That's not to say there's some merit to all of this. It's just that people shouldn't be as astonished by these results as they are. It's complexity theory. There's literally no such thing as a hard wall where something is nlogn in time and can't get lower. It can always get lower. But you need both the time and space complexities together to reason about this.
Like, there exist problems that have a lower bound of n time where algorithms can get arbitrarily close to O(n) complexity but there is no program that actually reaches it (there is one that runs in time O(n^{1.1}), one that runs in O(n^{1.01}), etc).
But that doesn’t mean that there aren’t hard walls, it just means there are hard walls where every program’s runtime is > that wall, rather than >= that wall. But maybe I’m misunderstanding, or there are some corollaries I’m missing?
As an aside, as someone who studied more on the pure math side, Blums speed up theorem is rather intuitive. It looks like there might be a relatively elegant proof using topology. Blums speed up theorem is basically just a statement that the set of programs that implement a particular computable function doesn’t satisfy the greatest lower bound property. This is also the case for, for example, the set of rational numbers: there exist subsets of the rational numbers with a lower bound but not a greatest lower bound (like the set of all positive rational numbers q where q^2 >= 2). I’m hand waving, but I think in that same vein you can show that the set of programs under the topology of ordering by runtime is completely disconnected.
Isn't this an ironic example to use, since one of the only lower bounds we have actually found is nlogn for comparison-based sorting?
And anyways, this point seems too strong: the fact that TCS people believe NP != P is another example that we believe a lower bound exists, no? (And relatedly, the large portion of TCS that is dedicated to trying to figure out how to lower-bound anything, while admittedly not so successful yet, shows that researchers believe lower bounds exist. I mean, any complexity class non-equality hypothesis is an example of this, no?)
Not always, isn't it? The theorem says that there exists a function that can be sped up, but not that every function can be. A trivial counter example would be the identity function on a TM. It's simply a HALT/ACCEPT. There's no way to reduce that.
The space/time trade-off is also not infinitely flexible, since it takes time to fill space. And lookup tables have to be constructed at run-time, or they'll be of finite size, and hence only a constant speed-up. Perhaps you were thinking of that theorem, the linear as wikipedia calls it? https://en.wikipedia.org/wiki/Linear_speedup_theorem
If you don't like that convention, you are free to use your own, but it is going to confuse people who use the standard convention. And the convention makes a lot of sense when you stop and think about the problem that people are trying to solve.
But your right in that we don’t have a huge LUT as it’s not worth it.
Small one in the ALU though, for partial products to add can be worth the additional wire length.
You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.
A 2^64bits lookup table only has O(1) lookup if you ignore the impossibility of creating a machine that has 2 exabytes of storage where all those bytes have the same access time. Or you'd have to redefine O(1) to be “at most the worst case”. But strictly speaking from the mathematical definition it’s O(1). Which is why no one in practical engineering takes most complexity results seriously as the entire field maps to practice poorly precisely for these reasons (all our machines use fixed integer math and have limited tape storage)
The whole point of complexity theory is that there are no bounds on input size.
That's just incorrect. Are you assuming the table starts pre-filled, and has O(1) lookup? Nobody is using a model like that for this problem.
2^n space complexity doesn't automatically mean you get to fill that space with 2^n chosen computed values for free.
There's models with "oracle"s for various sub-problems and such (that's essentially what you're describing as the ability you're baking in to your model of computation, it can look up the answer to any multiplication for free), but that's not an interesting model for this problem.
If you do that you're just asking "hey, how long does it take to multiply two numbers if multiplying two numbers is free". Boring question, and not the one anyone else is asking.
I guess you're saying that this holds in "realistic" computational models? Sorting in the decision tree model is famously \Omega(n log n)-time.
number multiplication is basically convolution and closely tied with FFTs, so I wouldn't personally be surprised even if a lot of the "FFT's work" could somehow be stuffed into exact arithmetic operations, and the remaining costs just track the packing and unpacking from that representation. It's just an exploit of the book-keeping.
That's ignoring the other complaints about this being a galactic algorithm.
Similarly, yes, it's a galactic algorithm, but these things are still viewed as meaningful. The fact that it is even possible at all with a unit cost RAM asymptotically is an incredible result that nobody expected.
One can of course make a puzzle out of anything, but it behooves asking what situation is being modelled by that problem.
And yes, this criticism might apply more broadly to TCS rather than just this specific artifact from OpenAI. It's reward hacking regardless of whether humans do it or LLMs.
Also the 10^-13 isn't an optimized number. Current results are up about 10 orders of magnitude (10^-3) and show little sign of stopping. it's seems entirely plausible that we might get to nsqrt(log(n)) (with a likely still astronomical constant)
But isn't the assumption that arithmetic is "atomic" standard in TCS? Costs do scale with the bit length, presumably they aren't assuming that addition is "constant time" with respect to # of bits (which would defeat the whole point of the exercise).
Maybe I'm missing something, but none of the things mentioned in that blogpost seem particularly "surprising" to me, most of it focuses on the fact that computational models used in TCS don't align with the real-world model of computers, but that seems like something you learn in day 1 of algorithm analysis? If you want something closer to real-world you'd use word ram model.
One can do some interesting things in this model, such as the van Emde Boas data structure for O(log log n) integer set queries, and tricks where O(log n) size subproblems are converted to lookup tables.
Whether it's an oversight in just this work, or TCS more broadly, I do not know. But it's a fundamental point nonetheless.
Did they start with OpenAI's Lean proof and continue work on that?
Does the Lean proof grow significantly, or are they also trying to keep the Lean proof short-ish?
Engineers don't have to know why something worked in particular in order to use it, they just do.
Science later tries to figure that out.
Both are valuable, but the idea that science must be "first" is, at best, unsupported by the evidence.
https://nitter.kareem.one/RohanArun/status/21093360158149592...
(Replace top-level with healthy instances or x.com as needed)