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

Direct sums in randomized communication complexity. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao.
2-Source extractors under computational assumptions and cryptography with defective randomness. Xin Li, Anup Rao, and Yael Tauman Kalai.
Poisson matching. A. E. Holroyd, R. Pemantle, Y. Peres & O. Schramm.
Random sorting networks. O. Angel, A. E. Holroyd, D. Romik & B. Virag.
A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks. Omer Angel, Abraham D. Flaxman, and David B. Wilson.
Convergence of local dynamics to balanced outcomes in exchange networks. Yossi Azar, Ben Birnbaum, Elisa Celis, Nikhil Devanur and Yuval Peres.
On the geometry of graphs with a forbidden minor. James Lee and T. Sidiropoulos.
On the value of multiple read/write streams for approximating frequency moments. Paul Beame and Dang-Trinh Huynh-Ngoc.
Simon's Algorithm, Clebsch-Gordan Sieves, and Hidden Symmetries of Multiple Squares. Dave Bacon.
Eigenvalue bounds, spectral partitioning, and metric deformations via flows. Punya Biswal, James Lee and Satish Rao.

Revenue maximization in second-price ad auctions. Yossi Azar, Ben Birnbaum, Anna Karlin and C. Thach Nguyen.
Optimal algorithms and inapproximability results for every CSP? Prasad Raghavendra. Winner of Best Paper award and Best Student Paper award at STOC 2008.

Recent Classes

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

Analytical and geometric methods in the theory of computation

Advanced computational complexity

Algorithms and Economics of Networks

Geometric embeddings and high-dimensional phenomena

Error-Correcting Codes: Constructions and Algorithms

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.

UW-MSR Theory Center