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].

  • Lecture notes/homeworks: 50%
  • Project: 50%

    Here are some project ideas.

    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