The motivation for this class is that there are three research programs, pursued by largely distinct communities, which share the same mathematical core:
- Designing approximation algorithms for sparsest cut
- Giving explicit constructions of expander graphs
- Bounding the mixing time of random walks
(1) is a major theme in the study of approximation algorithms; regarding (2), there are combinatorial constructions, which have been studied by complexity theorists, and algebraic constructions, which rely on group theory but of the kind studied not by pure group theorists but rather by ergodic theorists or by analytic number theorists; solving questions of type (3) is the key to analyzing algorithms that follow the Markov-Chain Monte-Carlo scheme, and it is an active area of study in statistics and in theoretical computer science.
All three research programs, however, are ultimately concerned with studying the expansion of certain graphs, and have several mathematical techniques in common.
Cheeger’s inequality, for example, plays an important role in each of the three. In (1) it proves that the spectral partitioning algorithm provides a non-trivial approximation to the sparsest cut problem; in (2) it shows that in order to construct graphs with good edge-expansion it is sufficient to construct graphs with good eigenvalue separation; in (3) it shows that in order to prove that a graph has quick mixing time it is sufficient to prove that it has good edge-expansion.
This course will provide a unified presentation of these three areas.
Last summer, I gave a 20-hour version of this course at the University of Salerno which, if I say so myself, went really well, and I hope that the 30-hour version that I will start teaching at Stanford tomorrow will be a lot of fun. Watch this space for the lecture notes.