Simpler and Faster Spectral Sparsification for Eulerian Directed Graphs

While spectral sparsification is well understood for undirected graphs, developing efficient algorithms for spectral sparsification of Eulerian (directed) graphs has been challenging. We present a new framework for sparsifying Eulerian graphs that utilizes electrical routings to preserve Eulerianness, and exploits a simple effective resistance partitioning for improved sparsifier quality. Our approach yields state-of-the-art algorithms for constructing Eulerian sparsifiers, both in terms of running time and the resulting sparsity. As a consequence, we obtain significantly faster algorithms for solving directed Laplacian systems and computing stationary distributions of markov chains. This is joint work with Arun Jambulapati, Aaron Sidford, Kevin Tian, and Yibin Zhao.