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
My recent interests include fast approximation algorithms and machine learning augmented online algorithms.
My research is supported by NSF grant CCF-1566356 (NSF CRII Award), CCF-1717134 and CCF-1844890 (NSF Career Award).
Teaching
- Teaching currently (Spring 2022): CSE431/531: Analysis of Algorithms I
- CSE431/531: Analysis of Algorithms I (Fall 2021, Spring 2021, Spring 2020, Spring 2019, Spring 2018, Fall 2016, Spring 2016)
- CSE 632: Analysis of Algorithms II (Topics Vary) (Fall 2017, Fall 2019, Fall 2020)
- CSE7xx Seminars (Topics Vary) (Fall 2015, Fall 2018, Fall 2019)
- EECS336: Design and Analysis of Algorithms at Northwestern University (Winter 2015)
- co-taught Information and Coding Theory at TTIC with Madhur Tulsiani (Fall 2014)
PhD Advisees
- Xiangyu Guo
- Yunus Esencayi
- Jiayi Xian
Publications
Below is a sampled list of my publications. Full list of my publications.
- S. Li, Nearly-Linear Time Approximate Scheduling Algorithms, Manuscript
- Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboardi, S. Li and Di Wang, On Facility Location Problem in Local Differential Privacy Model, AISTATS 2022
- S. Li and Bundit Laekhanukit, Polynomial Integrality Gap of Flow LP for Directed Steiner Tree, SODA 2022
- S. Li and Jiayi Xian, Online Unrelated Machine Load Balancing with Predictions Revisited, ICML 2021, long presentation
- Xiangyu Guo, Janardhan Kulkarni, S. Li and Jiayi Xian, Consistent k-Median: Simpler, Better and Robust, AISTATS 2021
- S. Li, Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms, SODA 2021
- Xiangyu Guo, Janardhan Kulkarni, S. Li and Jiayi Xian, On the Facility Location Problem in Online and Dynamic Models, APPROX 2020
- Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, S. Li, Daniel Vaz and Jiayi Xian, On Approximating Degree-Bounded Network Design Problems, APPROX 2020
- Di Wang, Xiangyu Guo, Chaowen Guan, S. Li and Jinhui Xu, Estimating Stochastic Linear Combination of Non-linear Regressions, AAAI 2020
- Janardhan Kulkarni, S. Li, Jakub Tarnawski and Minwei Ye, Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints, SODA 2020
- Yunus Esencayi, Marco Gaboardi, S. Li and Di Wang, Facility Location Problem in Differential Privacy Model Revisited, NeurIPS 2019
- Fabrizio Grandoni, Bundit Laekhanukit and S. Li, O(log2k/loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm, STOC 2019, invited to a special issue of SICOMP
- Michael Langberg, S. Li, Sai Vikneshwar Mani Jayaraman and Atri Rudra, Topology Dependent Bounds for (Some) FAQs, PODS 2019
- Shashwat Garg, Janardhan Kulkarni and S. Li, Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time, SODA 2019
- S. Li, On Facility Location with General Lower Bounds, SODA 2019
- Uri Feige, Janardhan Kulkarni and S. Li, A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time, SODA 2019
- Xiangyu Guo and S. Li, Distributed k-Clustering for Data with Heavy Noise, NeurIPS 2018, Spotlight
- Ravishankar Krishnaswamy, S. Li and Sai Sandeep, Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding, STOC 2018
- S. Li, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, FOCS 2017, invited to a special issue of SICOMP
- Deeparnab Chakrabarty, Sanjeev Khanna and S. Li, On (1,ε)-Restricted Asgsignment Makespan Minimization, SODA 2015
- S. Li and Ola Svensson, Approximating k-Median via Pseudo-Approximation, STOC 2013
- Julia Chuzhoy and S. Li, A Polylogarithmic Approximation for Edge-Disjoint-Paths with Congestion 2, FOCS 2012, co-winner of best paper award
- S. Li, A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem, 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, SODA 2021, ICALP 2021, APPROX 2021, STOC 2022
- 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