79 citations · 306 across the 34 of their papers we have counts for
Showing 2016 · cs.CCShow all
2 papers · 2 filters
cs.CC2016
Paraunitary Matrices, Entropy, Algebraic Condition Number and Fourier Computation
Nir Ailon
The Fourier Transform is one of the most important linear transformations used in science and engineering. Cooley and Tukey's Fast Fourier Transform (FFT) from 1964 is a method for…
cs.CC2016
The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform
Nir Ailon, Gal Yehuda
The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a…