CATS-Oct-6-2016
Title[edit]
Computing the Stationary Distribution
Speaker[edit]
Michael Cohen
Abstract[edit]
Given an explicit description of a Markov chain, we present a new algorithm to (approximately) compute its stationary distribution. The traditional approaches to this problem involve either solving general systems of linear equations--taking n^{omega} time--or in some way simulating the Markov chain itself--giving a linear dependence on the mixing time of the Markov chain. In contrast, our new approach is an iterative method with a polylogarithmic dependence on mixing time, and is inspired by spectral graph theory methods from undirected graphs. Our methods can also be used for other random walk problems, such as Personalized Page Rank and commute times.
Joint work with Jonathan Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu.
Work presented at FOCS 2016
Bio[edit]
Michael Cohen is a graduate student in algorithms, advised by Jonathan Kelner and Alexander Madry. He is particularly interested in the use of techniques from linear algebra, convex optimization, and spectral graph theory in theoretical computer science.
