BARC talk by Thatchaphol Saranurak

Monday, 27 June 2022, Thatchaphol Saranurak, assistant professor at the University of Michigan, USA, will give a talk on "All-pairs minimum cuts in nearly quadratic time: a tutorial".

Title:
All-pairs minimum cuts in nearly quadratic time: a tutorial

Abstract:
We recently showed an algorithm for computing all-pairs minimum cuts (or, more precisely, the Gomory-Hu tree) in ~O(n^2) time in weighted graphs and even  almost-linear time in unweighted graphs. For weighted graphs, this is the first improvement over the 60-year-old algorithm by Gomory and Hu. Thus, surprisingly, computing all-pairs minimum cuts seems to be strictly easier than computing all-pairs shortest paths, which is conjectured to require n^{3-o(1)} time.

Thatchaphol will give a tutorial on the techniques behind our new result, one of which is called "isolating cuts". Then, he will survey recent progress in fast minimum cut algorithms and discuss open problems.

Joint work with Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, and Ohad Trabelsi.

Bio:
Thatchaphol Saranurak is an assistant professor in the Computer Science and Engineering Division at the University of Michigan. He received a Ph.D. in Computer Science from KTH Royal Institute of Technology in 2018, where I was fortunate to be advised by Danupon Nanongkai. Between 2018-2020, he was a research assistant professor at Toyota Technological Institute at Chicago.