CSC 574: Markov Chains (seminar in theory of computation)

Instructor: Daniel Stefankovic

Tuesday-Thursday 2:00pm-3:15pm in CSB 703

• Th 01/19 introduction
• Tu 01/24 linear algebra, probability theory review
• Th 01/26 cover time I
• Tu 01/31 cover time II
• Th 02/02 mixing time
• Tu 02/07 coupling, colorings using coupling
• Th 02/09 sampling <-> counting connection, sampling spanning trees
• Tu 02/14 sampling spanning trees (using coupling)
• Th 02/16 path coupling, application to colorings
• Tu 02/21 #P hardness, torpid mixing
• Th 02/23 independent sets (using path-coupling)
• Tu 02/28 coupling from the past (application to independent sets)
• Th 03/02 Ising model - coupling from the past
• Tu 03/07 Ising model - phase transition
• Th 03/09 dimer model (permanent) for planar graphs
• Tu 03/14 no class (spring break)
• Th 03/16 no class (spring break)
• Tu 03/21 (Markovian) coupling doesn't work for the permanent chain
• Th 03/23 conductance, canonical paths
• Tu 03/28 permanent (dense 0,1-matrices)
• Th 03/30 permanent (general 0,1-matrices, general non-negative matrices)
• Tu 04/04 Ising model in the low temperature region
• Th 04/06 lattice colorings, Potts model
• Tu 04/11 sampling from a convex body (survey of results)
• Th 04/13 counting linear extensions of a poset (reduction from volume, using coupling)
• Tu 04/18 sampling contingency tables, counting contingency tables
• Th 04/20 Fourier transform methods (applications to card shuffling)
• Tu 04/25 stopping time (applications to card shuffling)
• Th 04/27 counting knapsack solutions
• Tu 05/02 decomposition theorems, log Sobolev inequalities

Other possible topics:

• continuous time Markov chains
• simulated annealing
• simulated tempering

Books

• No book is required. Here are some relevant books (all have been placed on a 1-day reserve in Carlson):

• Counting, Sampling and Integrating (Algorithms and Complexity Series),
  M. Jerrum, ISBN: 3764369469.
• Matrix Analysis,
  R. Horn, C. Johnson, ISBN: 0521386322
• Randomized Algorithms,
  R. Motwani, P. Raghavan, ISBN: 0521474655
• Probability and Computing : Randomized Algorithms and Probabilistic Analysis,
  M. Mitzenmacher, E. Upfal, ISBN: 0521835402
• Finite Markov Chains and Algorithmic Applications,
  O. Haggstrom, ISBN: 0521890012
• Probabilistic methods for algorithmic discrete mathematics,
  ISBN: 3540646221

MCMC courses

• Eric Vigoda 2003 (University of Chicago)
• Dorit Aharonov 2002 (Hebrew University)

Preprints/reprints/tutorials

• D. Aldous, J. Fill: Reversible Markov Chains and Random Walks on Graphs
• A. Frieze
• M. Jerrum
• R. Kannan
• L. Lovasz (see surveys and publications)
• Y. Peres
• D. Randall (see talks and publications)
• A. Sinclair
• P. Tetali
• D.B. Wilson: Perfectly Random Sampling with Markov Chains