Ph.D. Student
Department of Electrical Engineering and Computer Science
Northwestern University
I will join Toyota Technological Institute at Chicago as a research assistant professor in Sep 2023. My new webpage: https://lirenshan.github.io/
I am currently a fifth-year Ph.D. student in the Theory Group at Northwestern University, advised by Prof. Konstantin Makarychev. Before that, I was an undergrad at Fudan University, where I was advised by Prof. Zhongzhi Zhang. Here is my CV.
Research Interest
I have a broad interest in various aspects of theoretical computer science and mathematics. My research interests include approximation algorithms, graph theory, and algorithmic game theory. The aim of my research is to design algorithms for data analysis and decision-making in real-world problems. I currently focus on clustering and graph partitioning problems.
Papers
Error-Tolerant E-Discovery Protocol. CSLAW 2024.
[Jinshuo Dong, Jason D. Hartline, Liren Shan, Aravindan, Vijayaraghavan]
Approximation Algorithm for Norm Multiway Cut. ESA 2023. [Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan]
Random Cuts are Optimal for Explainable k-Medians. Neurips 2023 (oral). [Konstantin Makarychev, Liren Shan]
Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA 2024. [Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan] (20 mins video, 1 hour video)
Fair Curing and Network Design in SIS Epidemic Processes. manuscript. [Yuhao Yi, Liren Shan, Philip E. Paré, Karl H. Johansson]
Optimal Scoring Rules for Multi-dimensional Effort. COLT 2023. [Jason D. Hartline, Yingkai Li, Liren Shan, Yifan Wu]
Algorithmic Learning Foundations for Common Law. CSLaw 2022. [Jason D. Hartline, Daniel W. Linna Jr., Liren Shan, Alex Tang]
Explainable k-means. Don’t be greedy, plant bigger trees! STOC 2022. [Konstantin Makarychev, Liren Shan] (20 min video)
Near-optimal Algorithms for Explainable k-medians and k-means. ICML 2021. [Konstantin Makarychev, Liren Shan] (5 min video)
Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models. SIAM Journal on Control and Optimization. [Yuhao Yi, Liren Shan, Philip E. Paré, Karl H. Johansson]
Improved Guarantees for k-means++ and k-means++ Parallel. NeurIPS 2020. [Konstantin Makarychev, Aravind Reddy, Liren Shan] (3 min video)
Optimization of Scoring Rules. EC 2022. [Yingkai Li, Jason D. Hartline, Liren Shan, Yifan Wu] (EC’ 2020 Best Poster, 1 min video, 20 min video)
Stochastic Linear Optimization with Adversarial Corruption. manuscript. [Yingkai Li, Edmund Y. Lou, Liren Shan]
Current Flow Group Closeness Centrality for Complex Networks. WWW 2019. [Huan Li, Richard Peng, Liren Shan, Yuhao Yi, Zhongzhi Zhang]
Improving Information Centrality of a Node in Complex Networks by Adding Edges. IJCAI 2018. [Liren Shan, Yuhao Yi, Zhongzhi Zhang]
Biharmonic Distance Related Centrality for Edges in Weighted Networks. IJCAI 2018. [Yuhao Yi, Liren Shan, Huan Li, Zhongzhi Zhang]
Independence Number and the Number of Maximum Independent Sets in Pseudofractal Scale-free Web and Sierpiński Gasket. Theoretical Computer Science. [Liren Shan, Huan Li, Zhongzhi Zhang]
Domination Number and Minimum Dominating Sets in Pseudofractal Scale-free Web and Sierpiński Graph. Theoretical Computer Science. [Liren Shan, Huan Li, Zhongzhi Zhang]
Robustness of First- and Second-Order Consensus Algorithms for a Noisy Scale-Free Small-World Koch Network. IEEE Transactions on Control System Technology. [Yuhao Yi, Zhongzhi Zhang, Liren Shan, Guanrong Chen]
Talks
SoCG Workshop on Recent Developments in Geometric Clustering June 13, 2023: Explainable k-means. Don’t be greedy, plant bigger trees!
IDEAL Workshop on Machine Learning, Interpretability, and Logic, Apr 14, 2023: Explainable k-means. Don’t be greedy, plant bigger trees!
Theory Seminar at University of Michigan, Jan 6, 2023: Higher-Order Cheeger Inequality for Partitioning with Buffers
Chicago Junior Theorists Workshop, Jan 5, 2023: Higher-Order Cheeger Inequality for Partitioning with Buffers (video)
University of Science and Technology of China, May 26, 2022: Explainable k-means. Don’t be greedy, plant bigger trees!
IDEAL Workshop on Clustering at Northwestern University, Apr 23, 2022: Explainable k-means. Don’t be greedy, plant bigger trees! (video)
Fudan University, Dec 18, 2021: Near-optimal Algorithms for Explainable k-medians and k-means
Northwestern University, Dec 2, 2020: Reducing the Spread of Infection in SIR Epidemic Models
Yahoo Research, Nov 5, 2020: Improved Guarantees for k-means++ and k-means++ Parallel
Academic Services
Reviewer: ICML 2021/2022/2023, NeurIPS 2021/2022/2023, AAAI 2022/2023/2024, ICLR 2022/2023, SODA 2023/2024, ICALP 2023, FOCS 2023, TCS, JAIR
Volunteer: STOC 2020, FOCS 2021
Awards
Terminal Year Fellowship, Northwestern University, McCormick School of Engineering, 2022
PhD Student Research Award, Northwestern University, Computer Science Department, 2022
Intern
Yahoo Research, Jun-Sep, 2022
Teaching Experience
Teaching Assistant: Design and Analysis of Algorithms, Northwestern University, 2019/2020/2021 Winter, 2021 Fall