Comment

Comment by ssivark

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.

parent ssivark 19 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton