Comment Re:"Tenfold"? (Score 1) 271
This result was rather interesting for SODA because it wasn't an improvement in time complexity over the best known algorithm. There are asymptotically faster previously known algorithms for computing sparse FFTs, but they aren't actually faster than the current (extremely optimized) FFT implementations unless the output is extremely sparse.
This algorithm isn't quite as asymptotically fast but it has a much better constant factor, so it is more likely to be effective in practice on inputs which are not extremely large and/or outputs which are not extremely sparse.