Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time.

Michael Kapralov

Browse the full STOC paper archive.