3 ms·
Title is inaccurate. The authors discovered (in 2019) an n log n algorithm for multiplication, but didn't prove n log n was optimal.
by scarmig 5y ago
Title is inaccurate. The authors discovered (in 2019) an n log n algorithm for multiplication, but didn't prove n log n was optimal.
- not2b 5y agoThis point is discussed in the article. And since the FFT is n log n, any faster algorithm would have to be completely different.
- ChrisLomont 5y agoThe article points out why n log n is optimal from information theory lower bounds.