Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity

Josh Alman, Kevin Rao

We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size $N$. For…