Jason Li

Teaching

Fall 2024: 15-451 Design and Analysis of Algorithms
Spring 2024: 15-850 Advanced Algorithms

Research Interests

My research applies modern algorithmic techniques to the hardest, longstanding open problems in the field of fast graph algorithms. To illustrate, here are some of my recent discoveries:

• the first almost-linear time algorithm for deterministic global minimum cut through the expander decomposition technique,
• the first almost-linear time all-pairs minimum cut (Gomory-Hu tree) algorithm through the isolating cuts framework and recent advances in dynamic graph algorithms, and
• the first nearly work- and time-optimal parallel algorithm for approximate shortest path through methods in continuous optimization.

These modern techniques are all variations of two recurring themes, preconditioning and locality, which I explore in my thesis below. Loosely speaking, I see preconditioning and locality as reductions from worst-case instances to well-behaved and local instances, respectively.

Thesis: Preconditioning and Locality in Algorithm Design
EATCS Distinguished Dissertation Award (2021)
[slides]

My Amazing Students

Henry Fleischmann   George Li

Selected Publications (show all)

All Publications (show selected)

Contact

Office: GHC 5011

Email: jm[my last name]@cs.cmu.edu

Advice on cold-emailing for research: If you are a student at CMU and/or you have worked with my recent collaborators, feel free to cold-email me asking for research opportunities and I will try my best to accommodate your request. Otherwise, please be aware that I receive many such emails on a weekly basis, and it is infeasible for me to reply to all of them. For initiating collaborations with no prior connections, my best advice is the following: read up on the person's work, improve or simplify one of their results, and email the improvement to them. Even a small improvement shows that you are committed to research, and most professors will gladly take the opportunity to work with a dedicated and promising student.