Graph Partitioning and Expanders

In addition to a class on optimization, this term I am very excited to teach a new class on graph partitioning and expanders, which I have been planning for a long time.

The motivation for this class is that there are three research programs, pursued by largely distinct communities, which share the same mathematical core:

  1. Designing approximation algorithms for sparsest cut
  2. Giving explicit constructions of expander graphs
  3. 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.

3 thoughts on “Graph Partitioning and Expanders

  1. Are you going to upload any scribes anywhere? It would be nice to read them, because topic seems really interesting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s