Speaker: Sushant Sachdeva the University of Toronto Department of Computer Science and a Vector Institute affiliate
Time: 2023-07-14 14:30-2023-07-31 09:50
Venue: FIT 1-315 or Tencent Meeting ID: 981-127-091

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.

In this talk, I will present some of our key ideas behind our recent work that gives almost-linear time algorithms for solving all convex flow problems on graphs. 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.

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

Joint work with Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, and Maximilian Probst Gutenberg.

Short Bio:

Sushant Sachdeva is a faculty member at the University of Toronto Department of Computer Science and a Vector Institute affiliate. 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. Before joining University of Toronto, he was a research scientist at Google. He completed his postdoc at Yale with Dan Spielman (2016), his PhD from Princeton (2013) under Sanjeev Arora, and his BTech from IIT Bombay (2008). He is a recipient of the Sloan Fellowship (2023), an IEEE FOCS Best Paper Award (2022), a Google Faculty Research Award (2017), a Simons Berkeley Research Fellowship (2013), and the President of India Gold Medal (2008).