6.896: Probability and Computation

Spring 2011

Recent years have seen a remarkable interplay between Computer Science and Probability. The ability of computers to toss coins has lead to algorithms that are more efficient, conceptually simpler and more elegant than their best known deterministic counterparts. At the same time, research in computation has influenced the questions and techniques of probability theory.

This class aims to study advanced probabilistic techniques and their applications in computation, drawing examples from algorithms, random structures and combinatorics. The main focus of the class will revolve around Markov chain Monte Carlo theory and applications, Statistical Physics and applications to Phylogenetics, and, if time permits, Harmonic Analysis of Boolean functions and applications to Computational Learning Theory, and Smoothed Analysis. A tentative syllabus is presented below.

Course Information

Course Outline

There is a significant dynamic component to the course, as topics drop in and out, or get longer or shorter treatment, depending on audience interest/reaction/resistence. We consider this a feature. Given this, here is a rough outline of the course material:


Please use the scribe template to produce your notes. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here .

List of Readings

Online Resources Other classes with useful resources: