Does anyone know if there's a simple way of understanding how exactly this speedup works? Standard O(N log N) multiplication uses frequency decomposition via FFT, iiuc; what might this construction look like?
The tldr is that you can turn a single fft into an n dimensional fft, into n 1d ffts and then share a very small amount of the work of the multiple ffts