Algorithms Seminar

Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs

Speaker:Richard Peng
Date: Thursday, November 17, 2016
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke

Abstract

We provide almost-linear time algorithms for computing various fundamental quantities associated with random walks on directed graphs, including stationary distributions, personalized PageRank vectors, hitting times between vertices, and escape probabilities. Previously it was unknown whether any of these can be computed to high accuracy more efficiently than solving an arbitrary linear system. Our results are based on efficiently reducing all of these problems to solving systems on Eulerian graphs, where all vertices have the same in/out degrees. Then we provide a notion of approximation for directed graphs, prove sparsifiers under this notion always exist, and show how to construct them in almost linear time. This talk is based on https://arxiv.org/abs/1608.03270 and https://arxiv.org/abs/1611.00755 which are joint works with Michael B. Cohen, Jon Kelner, John Peebles, Anup B. Rao, Aaron Sidford, and Adrian Vladu.

Biography

Richard Peng is an assistant professor in the school of computer science at the Georgia Institute of Technology. His main research interests are in the design, analysis, and implementation of efficient algorithms. Richard received his Ph.D. from Carnegie Mellon University in 2013 and was an instructor in applied math at the Massachusetts Institute of Technology until 2015. He was a Microsoft Research PhD Fellow and his thesis received the CMU SCS Distinguished Dissertation Award.

Hosted by:
Rong Ge