Lingxiao Huang's Homepage

Lingxiao Huang (黄棱潇)

Associate Professor 

Theory Group

School of Computer Science

Nanjing University, China

Email: huanglingxiao@nju.edu.cn

Address: Room 403, Department of Computer Science and Technology Building, Xianlin Campus, Nanjing University, Jiangsu Province, China, 210023 (南京大学仙林校区计算机科学与技术系楼403)

Education Background

2022 - now   Nanjing University, Associate Professor 

2020 - 2022 Huawei TCS Lab, Senior Researcher

2019 - 2020 Yale University, Postdoc, Advisor: Nisheeth K. Vishnoi and K. Sudhir

2017 - 2019 EPFL, Postdoc, Advisor: Nisheeth K. Vishnoi

2012 - 2017 IIIS, Tsinghua University, PhD, Advisor: Jian Li

2008 - 2012 IIIS, Tsinghua University, Bachelor

Research Interests

My research interests cover a variety of topics, including algorithms, machine learning, and computational social choice. I am passionate about constructing novel algorithms that are motivated by existing challenges in society and machine learning, such as

• Developing algorithms that ensure fairness.

• Constructing efficient data summaries in machine learning.

See e.g., notes https://zhuanlan.zhihu.com/p/619661335 and https://zhuanlan.zhihu.com/p/619672276 for more information.

I am currently seeking driven and self-motivated students who have a passion for exploring theory and algorithm design through research. Please do not hesitate to reach out to me via email if you are interested. 

Publications 

Mauscript

1. A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem. Zhang-Hua Fu, Sipeng Sun, Jintong Ren, Tianshu Yu, Haoyu Zhang, Yuanyuan Liu, Lingxiao Huang, Xiang Yan, Pinyan Lu. https://arxiv.org/abs/2308.04639

Published

2. Space Complexity of Euclidean Clustering. Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, Zengfeng Huang. SoCG2024, TIT2025 (Journal version).  https://arxiv.org/pdf/2403.02971.pdf. 

3. Near-Optimal Dimension Reduction for Facility Location. Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Di Yue. STOC2025. https://arxiv.org/abs/2411.05432 

4. On Optimal Approximations for k-Submodular Maximization via Multilinear Extension. Lingxiao Huang, Baoxiang Wang, Huanjian Zhou. ICLR2025 (spotlight). https://arxiv.org/abs/2107.07103 

5. Coresets for Clustering: General Assignment Constraints and Improved Size Bounds. Lingxiao Huang, Jian Li, Pinyan Lu, Xuan Wu. SODA2025. https://arxiv.org/abs/2301.08460

6. On Optimal Coreset Construction for Euclidean (k, z)-Clustering. Lingxiao Huang, Jian Li, Xuan Wu. STOC2024. https://arxiv.org/abs/2211.11923. Talk: https://www.youtube.com/watch?v=JJUAQHtlnX8

7. On Coresets for Clustering in Small Dimensional Euclidean Spaces. Lingxiao Huang, Ruiyuan Huang, Zengfeng Huang, Xuan Wu. ICML2023. https://arxiv.org/abs/2302.13737

8. The power of Uniform Sampling for K-Median. Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou. ICML2023. https://arxiv.org/abs/2302.11339

9. Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions. Niclas Boehmer, L. Elisa Celis, Lingxiao Huang, Anay Mehrotra, Nisheeth K. Vishnoi. ICML2023. https://arxiv.org/abs/2306.09835

10. Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching. Chang Liu, Runzhong Wang, Zetian Jiang, Junchi Yan, Lingxiao Huang, Pinyan Lu, ICLR2023. https://arxiv.org/abs/2012.08950

11. Near-optimal Coresets for Robust Clustering.  Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, Xuan Wu, ICLR2023 (notable-top-5%). https://arxiv.org/abs/2210.10394

12. Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering. Lingxiao Huang, Zhize Li, Jialin Sun, Haoyu Zhao, NeurIPS2022. https://arxiv.org/abs/2210.14664

13. Efficient Submodular Optimization under Noise: Local Search is Robust. Lingxiao Huang, Yuyi Wang, Chunxue Yang, Huanjian Zhou, NeurIPS2022. https://arxiv.org/abs/2210.11992

14. M-Mix: Generating Hard Negatives via Multi-sample Mixing for Contrastive Learning. Shaofeng Zhang, Meng Liu, Junchi Yan, Hengrui Zhang, Lingxiao Huang, Xiaokang Yang, Pinyan Lu, KDD2022. https://sherrylone.github.io/assets/KDD22_M-Mix.pdf

15. Coresets for Time Series Clustering.  Lingxiao Huang, K. Sudhir, Nisheeth K. Vishnoi, NeurIPS2021 (spotlight). https://arxiv.org/abs/2110.15263

16. Fair Classification with Noisy Protected Attributes: A Framework with Provable Guarantees. L. Elisa Celis, Lingxiao Huang, Vijay Keswani, Nisheeth K. Vishnoi, ICML2021. https://arxiv.org/abs/2006.04778

17. Coresets for Regressions with Panel Data. Lingxiao Huang, K. Sudhir, Nisheeth K. Vishnoi, NeurIPS2020. https://arxiv.org/abs/2011.00981

18. Coresets for Clustering in Graphs of Bounded Treewidth. Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu, ICML2020. https://arxiv.org/abs/1907.04733

19. Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal. Lingxiao Huang and Nisheeth K. Vishnoi, STOC2020. https://arxiv.org/abs/2004.06263

20. Towards Just, Fair and Interpretable Methods for Judicial Subset Selection. Lingxiao Huang, Julia Wei, L. Elisa Celis, AIES2020. https://dl.acm.org/doi/pdf/10.1145/3375627.3375848 

21. Coresets for Clustering with Fairness Constraints. Lingxiao Huang, Shaofeng H.-C. Jiang, Nisheeth K. Vishnoi, NeurIPS2019. https://arxiv.org/abs/1906.08484

22. Stable and Fair Classification. Lingxiao Huang and Nisheeth K. Vishnoi, ICML2019. https://arxiv.org/abs/1902.07823 

23. Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees. L. Elisa Celis, Lingxiao Huang, Vijay Keswani, Nisheeth K. Vishnoi, FAT*2019. https://arxiv.org/abs/1806.06055 

24. Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu, FOCS2018. https://arxiv.org/abs/1804.02530

25. Multiwinner Voting with Fairness Constraints. L. Elisa Celis, Lingxiao Huang, Nisheeth K. Vishnoi, IJCAI-ECAI2018. https://arxiv.org/abs/1710.10057 

26. SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms. Lingxiao Huang, Yifei Jin, Jian Li, SWAT2018. https://arxiv.org/abs/1705.07252  

27. Capacitated Center Problems with Two-Sided Bounds and Ourliers. Hu Ding, Lingxiao Huang, Lunjia Hu, Jian Li, WADS2017. https://arxiv.org/abs/1702.07435 

28. Stochastic k-Center and j-Flat-Center Problems. Lingxiao Huang, and Jian Li, SODA2017. https://arxiv.org/abs/1607.04989 

29. Epsilon-Kernel Coresets for Stochastic Points. Lingxiao Huang, Jian Li, Jeff M. Phillips, Haitao Wang, ESA2016. https://arxiv.org/abs/1411.0194 

30. K-Means Clustering with Distributed Dimensions. Hu Ding, Lingxiao Huang, Jian Li, Yu Liu, ICML2016. http://jmlr.org/proceedings/papers/v48/ding16.pdf 

31. Canonical Paths for MCMC: from Art to Science. Lingxiao Huang, Pinyan Lu, Chihao Zhang, SODA2016. https://arxiv.org/abs/1510.04099 

32. Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points. Lingxiao Huang and Jian Li., ICALP2015. https://arxiv.org/abs/1209.5828

33. Approximation Algorithms for the Connected Sensor Cover Problem. Lingxiao Huang, Jian Li, Qicai Shi, COCOON2015; Theor. Comput. Sci. 2020. https://arxiv.org/abs/1505.00081

34. Egalitarian Pairwise Kidney Exchange: Fast Algorithms via Linear Programming and Parametric Flow. Jian Li, Yichang Liu, Lingxiao Huang, Pingzhong Tang, AAMAS2014. http://dl.acm.org/citation.cfm?id=2615804

35. The Multi-shop Ski Rental Problem. Lingqing Ai, Xian Wu, Lingxiao Huang, Longbo Huang, Pingzhong Tang, Jian Li. SIGMETRICS2014. https://arxiv.org/abs/1404.2671

Awards

2016 National Scolarship

2008 CMO Gold Medal