BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Thatchaphol Saranurak (University of Michigan)
DTSTART:20220518T170000Z
DTEND:20220518T180000Z
DTSTAMP:20260423T021012Z
UID:TCSPlus/40
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/40/"
 >All-pairs minimum cuts in nearly quadratic time: a tutorial</a>\nby Thatc
 haphol Saranurak (University of Michigan) as part of TCS+\n\n\nAbstract\nW
 e recently showed an algorithm for computing all-pairs minimum cuts (or\, 
 more precisely\, the Gomory-Hu tree) in $\\tilde{O}(n^2)$ time in weighted
  graphs and even almost-linear time in unweighted graphs. For weighted gra
 phs\, this is the first improvement over the 60-year-old algorithm by Gomo
 ry and Hu. Thus\, surprisingly\, computing all-pairs minimum cuts seems to
  be strictly easier than computing all-pairs shortest paths\, which is con
 jectured to require $n^{3-o(1)}$ time.\n\nI will give a tutorial on the te
 chniques behind our new result\, one of which is called "isolating cuts". 
 Then\, I will survey recent progress in fast minimum cut algorithms and di
 scuss open problems.\n\nJoint work with Amir Abboud\, Robert Krauthgamer\,
  Jason Li\, Debmalya Panigrahi\, and Ohad Trabelsi.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/40/
END:VEVENT
END:VCALENDAR