IMPROVED TIME BOUNDS FOR NEAR-OPTIMAL SPARSE FOURIER REPRESENTATIONS Martin J. Strauss University of Michigan We give a randomized algorithm that, given a discrete signal of length N and parameters t and epsilon, finds a t-term Fourier representation whose L2 error is at most 1+epsilon times worse than optimal. Previous randomized algorithms solved this problem in time polynomial in (t*log(N)/epsilon), which, for small t, is exponentially faster than the exact, deterministic FFT algorithm for a full Fourier decomposition. (In particular, these randomized algorithms cannot read the entire signal; they sample the signal.) Our new algorithm improves the time cost dependence on t from quartic or so to linear. Joint work with Anna Gilbert and S. Muthukrishnan. Some of this work was done while the speaker was at ATT Labs. Biography: Martin J. Strauss is an assistant professor in the math and EECS departments of the University of Michigan. He holds an A.B. degree from Columbia University and a PhD from Rutgers University, both in mathematics, and spent a year at Iowa State University and seven years at AT&T before joining the University of Michigan. He has written several articles in algorithms, complexity theory, cryptography, and computer security, mathematical approximation theory, and other topics. Dr. Strauss is currently interested in algorithms for massive data sets.