Theory Lunch Seminar - Jason Li October 30, 2024 12:00pm — 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