Rapidly Mixing Markov Chains, Fall 1996
Lecture Notes:
- Oct 9: Counting problems
- Oct 11: Motivation and Markov chains
- Oct 16: Some complexity classes
- Oct 18: Sampling matchings and Conductance
- Oct 21: Matchings cont.
- Oct 23: Canonical paths
- Oct 28, 30: The Jerrum-Sinclair algorithm for perfect matchings
- Nov 6: Couplings and sampling spanning trees
- Nov 11: Coupling for k-colorings
- Nov 13: Matchings on planar lattices
- Nov 18: Sampling tilings
- Nov 20: Couplings for routings
- Nov 25: Sampling Eulerian orientations
- Nov 27: Approximate counting and almost uniform generation