Research Interests
My main research area is algorithm design, a sub-area of theoretical computer science. More specifically, I design fast algorithms with provable guarantees under different computational models: offline, online, and dynamic algorithms, distributed algorithms and differential privacy. The problems I studied include both fundamental ones whose resolving can lead to advance of our algorithmic techniques, and those arising from modern applications:
- Clustering
- Facility Location
- Scheduling
- Network Routing and Design
Currently, I am interested in the use of linear programming hierarchy in improving the approximation guarantees for combinatorial optimization problems.
My research is supported by NSF grant CCF-1566356 (CRII), CCF-1717134 and CCF-1844890 (Career Award).
Teaching
- Spring 2021: CSE431/531: Analysis of Algorithms I
- Fall 2020: CSE632: Analysis of Algorithm II : Combinatorial Optimization and Linear Programming
- Fall 2019: CSE632: Analysis of Algorithms II : Randomized Algorithms
- Fall 2019: CSE 730 Seminar : Data Structures and Algorithms in Solving Programming Problems
- CSE431/531: Analysis of Algorithms I (Spring 2020, Spring 2019, Spring 2018, Fall 2016, Spring 2016)
- CSE711: Topics in Combinatorial Optimization and Linear Programming (Seminar) (Fall 2018)
- CSE 632: Analysis of Algorithms II : Approximation Algorithms (Fall 2017)
- CSE712: Advanced Topics in Algorithm Design (Seminar) (Fall 2015)
- EECS336: Design and Analysis of Algorithms (Winter 2015) at Northwestern University
- co-teaching Information and Coding Theory (Fall 2014) at TTIC with Madhur Tulsiani
PhD Advisees
- Xiangyu Guo
- Yunus Esencayi (co-advising with Prof. Roger He)
- Jiayi Xian (co-advising with Prof. Jinhui Xu)
- Alexander Stachnik
Publications
Below is a sampled list of my publications. Full list of my publications.
- Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms (arXiv)
S. Li
SODA 2021
- On the Facility Location Problem in Online and Dynamic Models (arXiv)
Xiangyu Guo, Janardhan Kulkarni, S. Li and Jiayi Xian
APPROX 2020
- On Approximating Degree-Bounded Network Design Problems (arXiv)
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, S. Li, Daniel Vaz and Jiayi Xian
APPROX 2020
- Estimating Stochastic Linear Combination of Non-linear Regressions
Di Wang, Xiangyu Guo, Chaowen Guan, S. Li and Jinhui Xu
AAAI 2020
- Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Janardhan Kulkarni, S. Li, Jakub Tarnawski and Minwei Ye
SODA 2020
- Differentially Private Facility Location Revisited (arXiv)
Yunus Esencayi, Marco Gaboardi, S. Li and Di Wang
NeurIPS 2019
- O(log2k/loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm (arXiv)
Fabrizio Grandoni, Bundit Laekhanukit and S. Li
STOC 2019
- Topology Dependent Bounds for (Some) FAQs
Michael Langberg, S. Li, Sai Vikneshwar Mani Jayaraman and Atri Rudra
PODS 2019
- Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
Shashwat Garg, Janardhan Kulkarni and S. Li
SODA 2019
- A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time (arXiv)
Uri Feige, Janardhan Kulkarni and S. Li
SODA 2019
- On Facility Location with General Lower Bounds (arXiv)
S. Li
SODA 2019
- Distributed k-Clustering for Data with Heavy Noise (arXiv)
Xiangyu Guo and S. Li
NeurIPS 2018 (Spotlight)
- Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding (arXiv)
Ravishankar Krishnaswamy, S. Li and Sai Sandeep
STOC 2018
- Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations (arXiv)
S. Li
FOCS 2017
invited to a special issue of SICOMP
- On (1,ε)-Restricted Asgsignment Makespan Minimization (arXiv)
Deeparnab Chakrabarty, Sanjeev Khanna and S. Li
SODA 2015
- Approximating k-Median via Pseudo-Approximation (arXiv)
S. Li and Ola Svensson
STOC 2013
- A Polylogarithmic Approximation for Edge-Disjoint-Paths with Congestion 2 (arXiv)
Julia Chuzhoy and S. Li
FOCS 2012
co-winner of best paper award
- A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem
S. Li
ICALP 2011
best student paper of Track A
Professional Activities
- PC member for APPROX+RANDOM 2017, SWAT 2018, MAPSP 2019, ISAAC 2019, TAMC 2020, ESA 2020(upcoming), SODA 2021(upcoming)
- Editorial Board Member of the ACM Transactions on Algorithms (since March 2019)
- Guest Editor of A Special Issue of Journal of Scheduling
- Local Committee Member of FWCG 2015