TCS+ talk: Wednesday, May 18 — Thatchaphol Saranurak, University of Michigan

by plustcs

The next TCS+ talk will take place this coming Wednesday, May 18th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Thatchaphol Saranurak from University of Michigan will speak about “All-pairs minimum cuts in nearly quadratic time: a tutorial ” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

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.

I will give a tutorial on the techniques behind our new result, one of which is called “isolating cuts”. Then, I 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.