Random walks and Algorithms

Time and location: Thursdays at 13:35, Room 1

Tentative Syllabus:
1. Random walks on the lattice. CLT. Recurrence vs. transience and Polya's theorem (here), the Nash-Williams creterion (chapter 2.5 here).
2. Graph Geomerty: Growth, Isoperimetry and graph limits (In these notes)
3. Random walks on graphs. Expansion and mixing. Spectra of graphs. Expander graphs. Most of it can be found in these lecture notes.
4. Volume estimation using random walks, based on these notes.
5. Discrepancy minimization via random walks. More or less this paper.
6. Graph clustering via random walks. Probably this paper.

Homework assignment exercises: here.