CS 8803 MCM: Markov Chain Monte Carlo Algorithms

Special Topics Course, Spring 2010

Markov chains, or random walks on graphs, are fundamental tools used for approximation algorithms, counting algorithms, combinatorial optimization and estimating various quantities associated with a large combinatorial set. They arise in applications from statistical physics, biology, economics, web analysis, vision, and across many other scientific disciplines.

In this course we will examine how Markov chains can be used in algorithms and we will study methods for making these algorithms provably efficient. There will be a special focus on problems arising from statistical physics and how insights from computing, mathematics and physics have contributed to many recent breakthroughs.

Time: Wednesday and Friday 12:00-1:30.

Prerequisites: A graduate course in probability theory and a graduate course in algorithms.

Useful references: Lectures:

Short projects:
Please read one of the following papers and write a short (3-4) page summary of the results and the main ideas. You will have the opportunity to give a 20 minute summary to the class the last week of classes. You can work along or in groups of 2.

Open problems / Projects (optional):

Course Outline: