IEOR-DRO Seminar: Aaron Sidford (Stanford)

November 21, 2017 | 1:10pm - 2:00pm

IEOR-DRO Seminar: Aaron Sidford (Stanford)

Mudd Hall, 500 W. 120 St., New York, NY 10027 303
Title: Faster Algorithms for Computing the Stationary Distribution
 
Abstract: Computing the stationary distribution of a Markov Chain is one of the most fundamental problems in optimization. It lies at the heart of numerous computational tasks including computing personalized PageRank vectors, evaluating the utility of policies in Markov decision process, and solving asymmetric diagonally dominant linear systems. Despite the ubiquity of these problems, until recently the fastest known running times for computing the stationary distribution either depended polynomially on the mixing time or appealed to generic linear system solving machinery, and therefore ran in super-quadratic time. 
 
In this talk I will present recent results showing that the stationary distribution and related quantities can all be computed in almost linear time. I will present new iterative methods for extracting structure from directed graphs and and show how they can be tailored to achieve this new running time. Moreover, I will discuss connections between this work and recent developments in solving Laplacian systems and optimizing over directed graphs. 
 
This talk reflects joint work with Michael B. Cohen (MIT), Jonathan Kelner (MIT), John Peebles (MIT), Richard Peng (Georgia Tech) and Adrian Vladu (MIT).
 
Bio: Aaron Sidford is an Assistant Professor at Stanford University's department of Management Science and Engineering and, by courtesy, of Computer Science. He received his PhD. in electrical engineering and computer science from MIT in 2015, where he was advised by Professor Jonathan Kelner. 
 
Aaron's research interests lie broadly in the theory of computation where his work focuses on the design of efficient algorithms for optimization. He is particularly interested in problems at the intersection of combinatorial and continuous optimization. Recently, his research has focused on improving the running time for solving classic problems in algorithmic graph theory while using and improving tools in disciplines ranging from numerical analysis to data structures to spectral graph theory.


500 W. 120th St., Mudd 315, New York, NY 10027    212-854-2942                 
©2014 Columbia University