Comment by hansvm
10 hours ago
Double-checking, is this more like the recent DFT improvement where even the word-RAM model of computation doesn't justify the fraction of a log factor they eliminated because of an assumption of arbitrary-precision arithmetic, or has ETH actually fallen with the Lean proof being formulated appropriately? Do we know yet?
The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).
That doesn't sound right. Previous results proved that with bounded values you couldn't beat O(nlogn), among other things. The OpenAI result explicitly used arbitrary-precision complex arithmetic. Yes, it's galactic [0], but either it's wrong or the previous results were wrong, no?
[0] Very much not something I care much about in these sorts of conversations. Even if it weren't galactic, a random logn factor here and there usually loses to cache efficiency and whatnot. Their speedups were less than that, and I'd already assumed we were in the realm of applied math rather than real engineering.
> but either it's wrong or the previous results were wrong, no?
Not quite. This result uses polylog(n) precision which isn't bounded, so it escapes the previous bounds. This doesn't noticably affect the runtime because not all of the math needs this extra precision (in this case you need a couple computations in higher precision but less than n operations), so the extra precision can be payed for even in a TM/circuit model.
Are you thinking of the int multiplication result instead? The DFT result uses a computation model with unlimited precision reals.
no. The DFT result as published uses unlimited precision, but the comparison with the int multiplication shows that the unlimited precision just makes the paper shorter/easier rather than being an exploit in the computation model.