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.
theory.epfl.ch/kapralov/
Hassanieh, Indyk, Katabi and Price (2012). Nearly Optimal Sparse Fourier Transfo
arxiv.org/pdf/1201.2501.pdf
Piotre Indyk and MIchael Kapralov (2014). Sample-Optimal Fourier Sampling in Any Constant Dimension
theory.epfl.ch/kapralov/papers...

[@Bm23CC]

Amazing video. These guys are so good at explaining stuff.

[@pwieczyk]

Good work, we need more guys like you on the YT.

[@png000]

your videos are so addictive, congratualtions!!!

[@frib75]

Could you just write the "formulas" (just "the algorithm speed goes in log n" or sth like that), just to make it easier to understand. I find "math" easier to understand when it's written down. Great video btw

[@fransmulder9326]

Great explanation!

[@SaMusz73]

Great to hear about the issues at the fringe of research. Who knew there was a better alg to look for than FFT !? This blew my mind ! Ignorance of the things we don't know we don't know ! (not a typo) ;) (I am currently wo rking on rats vocalisations analysis research in context of behaviour). Thank you both for this ray of light on the math aspects.

[@ArthurSonzogni]

Thank you!

[@itoverview-awesomeandroida1492]

Isnt FFT essentially an application of dynamic programmering. I mean isnt a recurrence relation is used for describing the DFT of N elements based og two N/2 dataset?

[@amitshtober1667]

Great! Thank you

[@realcygnus]

thank God for such geniuses !

[@dsgarden]

I have my doubts.

[@abel7749]

where is the original video

[@prismasasepaloalto1917]

please do more video's bud

[@dp0813]

Why are you using tau in place of pi? That's really confusing

[@jdubo1998]

Stop inventing shit, makes my life harder as a student.

[@samanthanewtons9025]

I can assure you this guy's knowledge about algorithms does not go beyond Codeforces Div3. Literally can't even teach decently.

[@hugol354]

Haha nice joke I had him as a teacher, a fucking God at teaching would like to be with him everyday