Markov Chain Monte Carlo Methods
Fall 2017, Georgia Tech
Tuesday and Thursday, noon-1:15pm, in Cherry Emerson room 320
Instructors: Eric Vigoda and Antonio Blanca
Office hours: Monday and Wednesday 10-11am in Klaus 2222
Textbooks:
Mark Jerrum's book
and
Markov Chains and Mixing Times by [Levin-Peres-Wilmer].
Grading:
Lecture notes/homeworks: 50%
Project: 50%
Here are some project ideas.
Lectures:
- Lectures 1-2 (8/22, 8/24):
Classical Exact Counting Algorithm
- Kasteleyn's poly-time algorithm for the Permanent of Planar graphs
Eric's notes and
scribe notes
- Lectures 3-4 (8/29, 8/31):
Hardness of Exact Counting
- Valiant's result: the Permanent is #P-complete
Eric's notes:
Part 1
and Part 2;
scribe notes
- Lectures 5-6 (9/5,9/7):
Markov Chains and Coupling Intro
- Eric's notes: Markov chain basics
and coupling;
scribe notes
- Lecture 7 (9/14):
Coupling example: Colorings
- Eric's notes;
scribe notes
- Lecture 8 (9/19):
Conductance
- Antonio's notes
- Lecture 9 (9/21):
Seminar by Andreas Galanis:
Random Walks on Small-World Networks
- Lecture 10 (9/26):
Spectral Gap
- Antonio's notes
- Lecture 11 (9/28):
Canonical Paths
- Eric's notes
- Lecture 12 (10/3):
Random Matchings
- Eric's notes
- Lecture 13 (10/5):
Random Perfect Matchings of Bipartite Graphs
- Eric's notes
- Lecture 14 (10/12):
Spectral Gap and Mixing Time
- Antonio's notes
- Lecture 15 (10/17):
Phase Transitions
- Eric's notes;
scribe notes
- Lecture 16 (10/19):
Swendsen-Wang Algorithm
- Antonio's notes
- Lecture 17 (10/24):
Bayesian inference for Phylogeny
- Eric's notes
- Lecture 18 (10/26):
Coupling from the Past
- Eric's notes
- Lecture 19 (10/31):
Random Spanning Tree
- Eric's notes
- Lecture 20 (11/2):
Coupling for Independent Sets
- Eric's notes
- Lecture 21 (11/7):
Phase transitions and Fast Mixing
- Antonio's notes
- Lecture 22 (11/9):
Volume Computation
- Santosh's notes and
scribe notes
- Lecture 23 (11/14):
Analysis of Ball Walk
- Eric's notes
- Lecture 24 (11/16):
Approximating the Partition Function
- Eric's notes