Many of you will be aware of the recent passing away of MIT graduate student Michael Cohen. At TCS+ we had asked Michael to give a talk; although he responded positively, he had also told us he’d want to wait for a really cool result to tell us all about.
The next TCS+ talk is dedicated to Michael’s memory. The talk will be given by Jon Kelner, from MIT, on work in which Michael played an important part (title and abstract below).
The talk will take place this coming Wednesday, November 29th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Jon Kelner will speak about “Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs“.
Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: 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. If time permits, I will also briefly discuss more recent work that improves the running time to be nearly linear, thereby eliminating the gap between the undirected and directed versions of these problems (up to polylogarithmic factors).
This talk is based on work with Michael Cohen, Rasmus Kyng, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu.