Hacker News Reader

It's potentially very interesting because there are a number of critical algorithms that are all related and share asymptotic lower bounds as a result. My first thought on seeing this was whether a proven result here would also open the door for FFTs to go below O(n log n).

View on HN

https://github.com/openai/math/blob/main/preprints/An-explic...

"We give a deterministic algorithm that computes the discrete Fourier transform at every length n in O ( n ( log ⁡ n ) ** (1 − 10 ** −13)) operations. The model uses exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost logarithmic-size indexing; scalar preparation and array organization are included."

This looks more like word salad instead of any other FFT algorithm paper I've seen, such as the tangent FFT paper that broke the lower bound previously established by split-radix. I'd have to defer to someone who might be able to decode this.

Reply on news.ycombinator.com