Adaptive sub-linear Fourier algorithms

N. Katz, An estimate for character sums , J. Amer. Math. Soc. 2

1989

Earlier work this paper cites.

M. Ajtai, H. Iwaniec, J. Komlós, J. Pintz, and E. Szemerédi, Construction of a thin set with small Fourier coefficients , Bull. London Math. Soc. 22

1990

Earlier work this paper cites.

I. Niven, H.S. Zuckerman, and H.L. Montgomery, An introduction to the theory of numbers , fifth ed., John Wiley & Sons Inc., New York, 1991

1991

Earlier work this paper cites.

A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data , SIAM J. Sci. Comput. 14

1993

Earlier work this paper cites.

E. Kushilevitz and Y. Mansour, Learning decision trees using the Fourier spectrum , SIAM J. Comput. 22

1993

Earlier work this paper cites.

N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transform, and learnability , J. Assoc. Comput. Mach. 40

1993

Earlier work this paper cites.

R. M. Karp, Probabilistic recurrence relations , J. Assoc. Comput. Mach. 41

1994

Earlier work this paper cites.

Y. Mansour, Randomized interpolation and approximation of sparse polynomials , SIAM Journal on Computing 24

1995

Earlier work this paper cites.

C. Anderson and M. D. Dahleh, Rapid computation of the discrete Fourier transform , SIAM J. Sci. Comput. 17

1996

Earlier work this paper cites.

Y. Wang and G. Zhou, On the use of high-order ambiguity function for multi-component polynomial phase signals , Signal Processing 65

1998

Earlier work this paper cites.

J. Dongarra and F. Sullivan, Guest editors’ introduction: The top 10 algorithms , Computing in Science and Engineering (2000), 22–23

2000

Cited alongside, same era.

O. Goldreich, D. Ron, and M. Sudan, Chinese remaindering with errors , IEEE Transactions on Information Theory 46

2000

Cited alongside, same era.

Y. Rubner, C. Tomasi, and L.J. Guibas, The earth mover’s distance as a metric for image retrieval , International Journal of Computer Vision 40

2000

Cited alongside, same era.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms , second ed., MIT Press, Cambridge, MA, 2001

2001

Cited alongside, same era.

D. Boneh, Finding smooth integers in short intervals using crt decoding , Journal of Computer and System Sciences 64

2002

Cited alongside, same era.

A. Gilbert, S. Muthukrishnan, and M. Strauss, Improved time bounds for near-optimal sparse Fourier representations , SPIE Wavelets XI, 2005

2005

Later among the works it cites.

T. Tao and V. Vu, Additive combinatorics , Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006

2006

Later among the works it cites.

M. Iwen, A. Gilbert, and M. Strauss, Empirical evaluation of a sub-linear time sparse DFT algorithm , Commun. Math. Sci. 5

2007

Later among the works it cites.

A. Gilbert, M. Strauss, and J. Tropp, A tutorial on fast Fourier sampling , IEEE Signal Processing Magazine 25

2008

Later among the works it cites.

M. Iwen, A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods , Proceedings of the nineteenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008, pp. 20–29