CSD Faculty Candidate
In Person and Virtual - ET - Newell-Simon 4305 and Zoom
JASON LI , Simons-Berkeley Postdoctoral Fellow, Simons Institute, University of California, Berkeley
Structure, Approximation, and Iteration for Graph Algorithms
Graphs are among the most well-studied objects in combinatorics and optimization, and are central to many areas of algorithm design.
In this talk, I describe some powerful new tools critical to recent progress on fundamental problems in graph algorithms, including long-standing problems such as all-pairs minimum cut, parallel shortest paths, and dynamic connectivity. Specifically, I demonstrate how the interplay between structure, approximation, and iteration forms the basis of my research process, and discuss how these ideas can lead to further breakthroughs.
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 paths 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.
Faculty Host: Richard Peng
In Person and Zoom Participation. See announcement.