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: 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 FleischmannGeorge Li

Selected Publications (show all)

  1. Congestion-Approximators from the Bottom Up.
    Jason Li, Satish Rao, Di Wang.
    SODA 2025. (arXiv)
  2. Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.
    Monika Henzinger, Jason Li, Satish Rao, Di Wang.
    SODA 2024. (arXiv)
    [slides@SODA]
    Best Paper
  3. All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.
    Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak.
    FOCS 2023.
  4. Undirected (1+ɛ)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms.
    Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li (r).
    STOC 2022. (arXiv)
  5. Approximate Gomory-Hu Tree Is Faster than n-1 Maxflows.
    Jason Li, Debmalya Panigrahi.
    STOC 2021. (arXiv)
    [slides@STOC]
  6. Vertex Connectivity in Poly-logarithmic Max-flows.
    Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai.
    STOC 2021. (arXiv)
  7. A Quasipolynomial (2+ɛ)-Approximation for Planar Sparsest Cut.
    Vincent Cohen-Addad, Anupam Gupta, Philip N Klein, Jason Li.
    STOC 2021. (arXiv)
  8. Deterministic Min-cut in Poly-logarithmic Max-flows.
    Jason Li, Debmalya Panigrahi.
    FOCS 2020. (arXiv)
    [conf-version] [slides@CMU(1h)]
  9. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
    Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak.
    FOCS 2020. (arXiv)
  10. The Karger-Stein Algorithm is Optimal for k-cut.
    Anupam Gupta, David Harris, Euiwoong Lee, Jason Li.
    STOC 2020. (arXiv)
    [conf-version] [slides1@STOC] [slides2@STOC]

Contact

Office: GHC 5011
Email: jm[my last name]@cs.cmu.edu
Advice on cold-emailing for research: