Faster than Fast Fourier Transform (ft. Michael Kapralov)

This video presents a recent breakthrough called the Sparse Fourier Transform (SFT). This algorithm yields an exponential speed-up over the celebrated Fast Fourier Transform (FFT) when asked to extract a small number of dominant Fourier coefficients. The video features Assistant Professor Michael Kapralov of the IC School at EPFL. http://theory.epfl.ch/kapralov/ Hassanieh, Indyk, Katabi and Price (2012). Nearly Optimal Sparse Fourier Transfo https://arxiv.org/pdf/1201.2501.pdf Piotre Indyk and MIchael Kapralov (2014). Sample-Optimal Fourier Sampling in Any Constant Dimension http://theory.epfl.ch/kapralov/papers...