Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity.

Josh Alman, Kevin Rao

Browse the full STOC paper archive.