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.

Time

2025-10-28  14:00 - 15:00

Speaker

Yibin Zhao, University of Toronto

Room

Room 602