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/ft-hd-part1.pdf

Видео Faster than Fast Fourier Transform (ft. Michael Kapralov) канала ZettaBytes, EPFL