Caltech Logo

TCS+ Talk

Wednesday, December 2, 2020
10:00am to 11:00am
Add to Cal
Online Event
Faster Algorithms for Unit Maximum Flow
Yang Liu, Stanford University,

Abstract: The maximum flow problem is one of the most well-studied problems in combinatorial optimization, encompassing a broad range of cut, matching, and scheduling problems. Here we present a recent line of work obtaining provably faster algorithms for solving the maximum flow problem using interior point methods. In particular, we show how to solve the maximum flow problem in m-edge unit capacity graphs in time almost m^(4/3), improving over the breakthrough m^(10/7) time algorithm of MÄ…dry.

This is based on joint work with Aaron Sidford (,

To watch the talk:

  • Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
  • Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)
For more information, please contact Bonnie Leung by email at