[CS] 2016-11-10 Jonathan Kelner
From Mike Donohoe
“Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs”
In
the analysis of Markov chains, there has been a longstanding algorithmic gap
between the general case, corresponding to random walks on directed graphs, and
the special case of reversible chains, for which the corresponding graph can be
taken to be undirected. This begins with the most basic computational
task, computing the stationary distribution, and persists for many of the
fundamental problems associated with random walks, such as computing hitting
and commute times, escape probabilities, and personalized PageRank
vectors. In the undirected case, there are algorithms for all of these
problems that run in linear or nearly-linear time, whereas it was unknown in
the directed case whether one could solve any of them more efficiently than an
arbitrary linear system.
More
broadly, this gap has its origins in a substantial discrepancy between the
state of algorithmic spectral graph theory in the undirected and directed
settings. While the undirected case has a richly developed theory and a
powerful collection of algorithmic tools, similar results have remained elusive
for directed graphs.
In this talk, I will begin to address this by giving an algorithmic framework that solves all of the problems listed above in almost-linear time. To do so, I will develop the first directed versions of several foundational primitives from undirected algorithmic spectral graph theory that had not been known to exist for directed graphs, notably including the first directed version of graph sparsification and an almost-linear-time solver for directed Laplacian systems.
This talk is based on work with Michael Cohen, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu.
Speaker:
Jonathan Kelner is an
Associate Professor of Applied Mathematics in the MIT Department of Mathematics
and a member of the MIT Computer Science and Artificial Intelligence Laboratory
(CSAIL). His research focuses on the application of techniques from pure
mathematics to the solution of fundamental problems in algorithms and
complexity theory. He was an undergraduate at Harvard University, and he
received his Ph.D. in Computer Science from MIT in 2006. Before joining the MIT
faculty, he spent a year as a member of the Institute for Advanced Study. He
has received a variety of awards for his work, including an NSF CAREER Award,
an Alfred P. Sloan Research Fellowship, the Best Paper Awards at STOC 2011,
SIGMETRICS 2011, and SODA 2014, the Harold E. Edgerton Faculty Achievement
Award, and the MIT School of Science Teaching Prize.
- Tags
-