Yibin Zhao: Closing the Gap Between Undirected and Eulerian Spectral Sparsification

Abstract

Although spectral sparsification is well understood for undirected graphs, developing efficient algorithms for Eulerian directed graphs — a key step towards efficient directed Laplacian solvers — has long been challenging. Eulerian sparsification requires preserving degree balance while controlling asymmetric matrix variances, making standard undirected techniques insufficient.

In this talk, I will present a line of my recent work that progressively closes this gap. I will describe how effective resistance decomposition and electrical routing enable efficient edge sampling, how matrix discrepancy theory helps reduce sparsity, and how degree-preserving patching graph combined with dynamic expander decomposition yields fully dynamic “Eulerian” sparsifiers. Together, these results bring the theory and efficiency of Eulerian sparsification much closer to that of the undirected setting.

This talk is based on joint works with Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Anvith Thudi, and Kevin Tian.

Speaker Bio

Yibin Zhao is a final-year PhD candidate at the University of Toronto, advised by Sushant Sachdeva. Previously, he received his B.S. degree in Computer Science from the University of Toronto. His research focuses on the design and analysis of fast algorithms, with particular interest in problems at the intersection of algorithmic graph theory, numerical linear algebra, and data structures.