Hacker News Reader

Comment by ssivark | Hacker News Reader

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.

View on HN

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.

Have we settled on a really good universal approximation model of memory+computation or is this a hard topic to solve in itself ?

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.

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)

Is that a natural barrier for the current method or we could also have n(log n)^epsilon ?

likely neither. The current bounds are very ad-hoc robot derived and definitely seem improvable. epsilon seems unlikely as there isn't an obvious reason why overhead should go to 0. I doubt we're anywhere near even being able to convincingly conjecture what the correct lower bound should be.

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

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.

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.

this fft result works in that model (although it becomes slightly more complicated)

Reply on news.ycombinator.com