CSE logo University of Washington Computer Science & Engineering
 CSE533: Harmonic Analysis for Complexity Theorists
  CSE Home    CSE 533 Home   About Us    Search    Contact Info 

Lecture Notes
 All Lectures
 Lecture 1
 Lecture 2
 Lecture 3
 Lecture 4
 Lecture 5
 Lecture 6
 Lecture 7
 Lecture 8
 Lecture 9
   

Harmonic Analysis for Complexity Theorists

Harmonic Analysis (often also called Fourier Analysis) is a classical field of mathematics. It originated in mathematical physics when Joseph Fourier sought to develop a mathematical theory of heat. It was later discovered to be a field rich in theory and extremely flexible and versatile in applications. It is a mainstay for all of mathematical physics. It has become one of the main parts of mathematical analysis and has found many applications in number theory. It also interacts beautifully with group theory and other parts of algebra.

In recent years it has been discovered that Harmonic Analysis can be very useful also in discrete mathematics and theoretical computer science. The purpose of this class is thus twofold: To offer a quick introduction to the classical theory and show you some of these more recent applications. We start with the classical theory since this is the most developed exemplar of the general theory. Also, it is a good source of inspiration when you try to push further the frontiers of the theory and when you seek new applications. The spectrum of possible applications in discrete mathematics seems very broad and many of these developments are still at an early stage, so it's not overly difficult to start doing reasech in these areas on one's own. Among the nice aspects of this area is that at least the classical theory is described beautifully in a number of books that combine crisp mathematical presentation with a broad range of applications as well as many entertaining stories and historical anecdotes. Enjoy!

Useful Books & References

  • Korner's "Fourier Analysis" is a good general reference.
  • Offner's "A Little Harmonic Analysis" is short and available here.
  • The following are good reads. All have similar names involving the words "Fourier" or "Harmonic" so only the authors are listed.
    • Dym & McKean
    • A. Terras (1st Volume)
  • The following are good reference books but not best for recreational reading.
    • Y. Katznelson
    • Helgason
  • Error-correcting codes
    • van Lint "Coding Theory"
  • Orthogonal polynomials
    • Davis "Interpolation and Approximation"
    • Szegö "Orthogonal polynomials"


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to cary]