Theory Lunch Seminar - Jason Li

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
JASON LI, Assistant Professor, Carnegie Mellon University
https://q3r.github.io/

Minimum cut problems are among the most well-studied questions in combinatorial optimization. In this talk, I will introduce a simple but powerful new tool for solving minimum cut problems called the minimum isolating cuts. I will show how this tool can be employed to obtain faster algorithms for several fundamental min-cut problems, namely global min-cut, Steiner min-cut, and all-pairs min-cut. For these problems, the new results represent the first improvement in their runtimes in several decades. 

These results are in collaboration with Amir Abboud, Robert Krauthgamer, Danupon Nanongkai, Thatchaphol Saranurak, and Ohad Trabelsi.

Add event to Google
Add event to iCal