Selected Work

Full publication list on Google Scholar

(α-β) stands for alphabetic order; (C) stands for contribution order; (S) stands for solo-author. 

Working Papers/ Manuscripts

• Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

(In submission)

(α-β) with Vladimir Braverman, Liudeng Wang, and Samson Zhou

2025

• Relative Error Fair Clustering in the Weak-Strong Oracle Model

42nd International Conference on Machine Learning (ICML), 2025

(α-β) with Vladimir Braverman, Prathamesh Dharangutte, Shaofeng Jiang, Hoai-An Nguyen, Yubo Zhang, and Samson Zhou

• Learning-Augmented Hierarchical Clustering

42nd International Conference on Machine Learning (ICML), 2025

(α-β) with Vladimir Braverman, Jon C. Ergun, and Samson Zhou

• Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time

28th International Conference on Artificial Intelligence and Statistics (AISTATS), 2025

(α-β) with Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai, and Vihan Shah

• On the Price of Differential Privacy for Hierarchical Clustering

13th International Conference on Learning Representations (ICLR), 2025

(α-β) with Chengyuan Deng, Jie Gao, Jalaj Upadhyay, and Samson Zhou

• Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap

39th Annual AAAI Conference on Artificial Intelligence (AAAI), 2025

(α-β) with Nikolai Karpov

2024

• Learning-augmented Maximum Independent Set

International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2024

(α-β) with Vladimir Braverman, Prathamesh Dharangutte, and Vihan Shah

• Metric Clustering and MST with Strong and Weak Distance Oracles

37th Annual Conference on Learning Theory (COLT), 2024

(α-β) with  MohammadHossein Bateni, Prathamesh Dharangutte, and Rajesh Jayaram

• The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits

37th Annual Conference on Learning Theory (COLT), 2024

(α-β) with  Sepehr Assadi

• The Discrepancy of Shortest Paths

51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024 

(α-β) with Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, and Jalaj Upadhyay

• Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024. 

(α-β) with  Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Nathan White, and Peilin Zhong

Ph.D. Dissertation (2024)

• Computational Learning Theory through a New Lens: Scalability, Uncertainty, Practicality, and Beyond

Ph.D. Dissertation 

2023

• Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost 

37th Conference on Neural Information Processing Systems (NeurIPS), 2023. 

(α-β) with  Sepehr Assadi and Vihan Shah

• Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance 

International Conference on Randomization and Computation (RANDOM), 2023.

(α-β) with  Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, and Jie Gao

• Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits

40th International Conference on Machine Learning (ICML), 2023. 

(S) Chen Wang

• Differentially Private Range Query on Shortest Paths

The Algorithms and Data Structures Symposium (WADS) 2023. 

(α-β) with Chengyuan Deng, Jie Gao, and Jalaj Upadhyay

2022

• Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity

36th Conference on Neural Information Processing Systems (NeurIPS), 2022. 

(α-β) with Sepehr Assadi

• Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds

35th Annual Conference on Learning Theory (COLT), 2022. 

(α-β) with Sepehr Assadi, Vaggos Chatziafratis, Jakub Łącki, and Vahab Mirrokni

• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

13th Innovations in Theoretical Computer Science (ITCS), 2022. 

(α-β) with Sepehr Assadi

2021

• On the Global Self-Attention Mechanism for Graph Convolutional Networks

25th International Conference on Pattern Recognition (ICPR)  (Oral),  2021. 

(C)  Chen Wang, Chengyuan Deng 

2020

• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits

52nd Annual ACM Symposium on Theory of Computing (STOC), 2020.

(α-β) with Sepehr Assadi

• SAG-VAE: End-to-end Joint Inference of Data Representations and Feature Relations

International Joint Conference on Neural Networks (IJCNN) (Oral), 2020. 

(C) Chen Wang, Chengyuan Deng, Vladimir Ivanov

• Imbalance-XGBoost: Leveraging Weighted and Focal Losses for Binary Label-Imbalanced Classification with XGBoost 

Pattern Recognition Letters, 2020. 

(C) Chen Wang, Chengyuan Deng, Suzhen Wang, 

2019 and before

• Scalar Quantization as Sparse Least Square Optimization

IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2019.

(C) Chen Wang, Xiaomei Yang, Shaomin Fei, Kai Zhou, Xiaofeng Gong, Miao Du, Ruisen Luo, 

• The Definition and Numerical Method of Final Value Problem and Arbitrary Value Problem

Computer Systems Science and Engineering, 2018(33)-5.

(C) Shixiong Wang, Jianhua He, Chen Wang, Xitong Li