Special Seminar - Jason Li, "Minimum Cuts and Preconditioning for Graph Algorithms"

Abstract:
Minimum cuts are among the most well-studied objects in combinatorial optimization. In this talk, I introduce an elegant but powerful new tool, the minimum isolating cuts, aimed at solving minimum cut problems. I show how this tool leads to a simple yet novel minimum cut algorithm, whose ideas formed the basis of a series of breakthroughs on minimum cut problems.

Next, I claim that minimum isolating cuts is one example of the general, algorithmic method of preconditioning. At a high level, preconditioning systematically reduces input instances of a problem to a smaller class of well-structured instances, which are then solved by a specialized algorithm. I survey my work on preconditioning-based algorithms and, finally, discuss my vision of preconditioning for the future.

Bio:
Jason Li is a Simons Institute postdoctoral fellow working on fundamental graph optimization problems such as minimum cut and maximum flow. His research efforts have led to state-of-the-art algorithms for a wide array of classic problems, including deterministic global minimum cut, minimum k-way cut, Gomory-Hu tree or all-pairs minimum cut, and single-source shortest path in parallel. He has received the EATCS Distinguished Dissertation Award, the Machtey Best Student Paper Award at FOCS 2019, and the Best Paper Award at ESA 2021.