Books

Markov Chain Mixing Time | by David A. Levin, Yuval Peres, and Elizabeth L. Wilmer

This book is an introduction to the modern approach to the theory of Markov chains. The main goal of this approach is to determine the rate of convergence of a Markov chain to the stationary distribution as a function of the size and geometry of the state space. The authors (including Yuval Peres of Microsoft Research) develop the key tools for estimating convergence times, including coupling, strong stationary times, and spectral methods. Markov Chains and Mixing Times is meant to bring the excitement of this active area of research to a wide audience.

Selected Recent Papers

Recent Classes

We also offer a variety of advanced theory courses (roughly one per quarter). Some recent ones:

Blogs

tcs math | by James R. Lee

This blog is an experiment in mathematical exposition. The focus is on mathematics that arises in theoretical computer science. The idea is to tell mathematicians about what goes on in TCS, as well as to introduce relevant mathematical techniques to theoretical computer scientists at large. Feedback is welcome.

The quantum Pontiff | by Dave Bacon

The Quantum Pontiff is a blog where some theoretical physicist who calls himself Dave Bacon pontifficates. Sometimes he makes sense, but often he seems like a raving loney. He has a particular fondness for anything to do with quantum theory, and saying silly things about the laws of the quantum world has been known to cause him to bash his head against his keyboard (which makes his neighbors rather concerned and causes funny bumps on his forehead.) Dave works in the field of quantum computing, which many computer scientists think of as physics and many physicists think of as computer science. Because his research area sits in between disciplines, he obtains an immense amount of pleasure watching the culture of physicists and computer scientists collide (Eat your heart out, C. P. Snow.) His sworn mortal enemy is Shtetl-Optimized which sucks for Dave because the Optimizer is a genius.