Selected Work

Full publication list on Google Scholar

(Author names of theory papers, indicated by *, are in alphabetic order)

Working Papers/ Manuscripts

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

In submission. 

* with  Sepehr Assadi

• Metric Clustering and MST with Strong and Weak Distance Oracles

In submission. 

* with  MohammadHossein Bateni, Prathamesh Dharangutte, and Rajesh Jayaram

2024

• 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

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. 

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

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. 

Chen Wang, Chengyuan Deng, Vladimir Ivanov

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

Pattern Recognition Letters, 2020. 

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.

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.

Shixiong Wang, Jianhua He, Chen Wang, Xitong Li