alt Hacker NewsIt'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).
Replies
osamagirl69 • today at 5:13 AM
[dead]
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."