Lingxiao Huang's Homepage

Lingxiao Huang (黄棱潇)

Associate Professor 

Theory Group

Department of Computer Science and Technology

Nanjing University, China

Email: huanglingxiao1990@126.com or 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. On Optimal Approximations for k-Submodular Maximization via Multilinear Extension. Lingxiao Huang, Baoxiang Wang, Huanjian Zhou. https://arxiv.org/abs/2107.07103

2. 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

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

Published

4. Space Complexity of Euclidean Clustering. Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, Zengfeng Huang. SoCG 2024. https://arxiv.org/pdf/2403.02971.pdf 

5. On Optimal Coreset Construction for Euclidean (k, z)-Clustering. Lingxiao Huang, Jian Li, Xuan Wu. STOC 2024. https://arxiv.org/abs/2211.11923

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

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

8. 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

9. 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

10. 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

11. 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

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

13. 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

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

15. 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

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

17. 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

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

19. 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 

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

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

22. 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 

23. 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

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

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

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

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

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

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

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

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

32. 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

33. 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

34. 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