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

Textbooks: Mark Jerrum's book and Markov Chains and Mixing Times by [Levin-Peres-Wilmer].

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

    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

    Lectures 5-6 (9/5,9/7): Markov Chains and Coupling Intro
    Eric's notes: Markov chain basics and coupling

    Lecture 7 (9/14): Coupling example: Colorings
    Eric's notes