Near-optimal sparse fourier representations via sampling.

Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss

Browse the full STOC paper archive.