Title: Almost linear time algorithms for all flows, even dynamic

Speaker:  Sushant Sachdeva, Associate Professor, University of Toronto Department of Computer Science

Abstract: Over the last decade or so, combining methods from continuous optimization and analysis with graph theoretic-insights has led to a revolution in algorithms for classic problems on graphs such as maximum flow and minimum cost flow.

In this talk, I will present some of the key ideas behind our recent works that give almost-linear time algorithms for solving all convex flow problems on graphs, even graphs that are dynamically changing. This implies almost linear time algorithms for max-flow, minimum-cost flow, bipartite matching, optimal transport, matrix scaling, isotonic regression, and several other well-studied problems on dynamic graphs. 

Our algorithms are designed using a new Interior Point Method (IPM) that solves the flow as a sequence of almost-linear number of approximate undirected minimum-ratio cycles / cuts, each of which is computed and processed very efficiently using new dynamic data structures.

Based on joint works with Jan van den Brand, Li Chen, Rasmus Kyng, Yang Liu, Richard Peng,  Simon Meierhans, Maximilian Probst Gutenberg, and Aaron Sidford.

Speaker Bio: Sushant Sachdeva is a faculty member at the University of Toronto Department of Computer Science and a Vector Institute faculty member. He is interested in Algorithms, and its connections to optimization, machine learning, and statistics. His recent research focus has been the design of fast algorithms for graph problems.

He is a recipient of the Infosys Award (2025), the Mclean Award (2025), a Sloan Fellowship (2023), an IEEE FOCS Best Paper Award (2022), a Google Faculty Research Award (2017), and a Simons Berkeley Research Fellowship (2013).