Research Interests

I am broadly interested in the power of parameterization in the context of algorithm design. In particular, I like understanding the mathematical structure of parameterized input instances, and how they can be exploited in the search for faster algorithms. Examples include, but are not limited to: On the mathematics side, my main interests are probabilistic and extremal combinatorics, and structural graph theory.

Biography

I am a third-year PhD student in the School of Computer Science at Carnegie Mellon University and am part of the Algorithms and Combinatorial Optimization (ACO) group. I am fortunate to be co-advised by Prof. Anupam Gupta and Prof. Bernhard Haeupler. I also obtained my bachelor's degree at CMU's School of Computer Science, with a double major in math.

Publications

  1. Anupam Gupta, Euiwoong Lee, Jason Li. The Number of Minimum k-Cuts: Improving the Karger-Stein Bound Submitted.
  2. Jason Li, Jesper Nederlof. Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time Submitted.
  3. Jason Li, Merav Parter. Planar Diameter via Metric Compression Submitted.
  4. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li. Tight FPT Approximations for k-Median and k-Means Submitted.
  5. Jason Li. Distributed Treewidth Computation Submitted. (arXiv)
  6. John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, Christian Scheideler. Distributed Computation in the Node-Congested Clique. Submitted. (arXiv)
  7. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk. Losing Treewidth by Separating Subsets. SODA 2019. (arXiv)
  8. Mohsen Ghaffari, Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms DISC 2018. (arXiv)
  9. Bernhard Haeupler, Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. DISC 2018. (arXiv)
  10. Anupam Gupta, Euiwoong Lee, Jason Li. Faster Exact and Approximate Algorithms for k-Cut. FOCS 2018. (arXiv)
  11. Bernhard Haeupler, Jason Li, Goran Zuzic. Minor Excluded Network Families Admit Fast Distributed Algorithms. PODC 2018. (arXiv)
  12. Anupam Gupta, Amit Kumar, Jason Li. Non-Preemptive Flow-Time Minimization via Rejections. ICALP 2018. (arXiv)
  13. Mohsen Ghaffari, Jason Li. Improved Distributed Algorithms for Exact Shortest Paths. STOC 2018. (arXiv)
  14. Anupam Gupta, Euiwoong Lee, Jason Li. An FPT Algorithm Beating 2-Approximation for k-Cut. SODA 2018. (arXiv)

Older Publications

Contact

Office: 7607 Gates Hillman Center, School of Computer Science, CMU
Email: jm[my last name]@cs.cmu.edu