Xue Chen
College of Computer Science
University of Science and Technology of China
Email: <myfirstname>chencs AT gmail DOT com
<myfirstname>chen1989 AT gmail DOT com
Research:
I am broadly interested in randomized Algorithms and pseudorandomness. Specific areas include big algorithms, learning theory, randomzied matrix algorithms, coding theory, and derandomization.
Bio: Recently, I joined the College of Computer Science in USTC. Before joining USTC, I was an assistant professor in the CS department of George Mason University. Previously, I obtained my Ph.D. in the University of Texas at Austin, fortunately advised by Professor David Zuckerman, and spent two years as a postdoc fellow in the theory group of Northwestern University. Prior to Austin, I received my bachelor's degree from the Yao Class at Tsinghua University.
Fourier transform and Sparse recovery
Xue Chen, Anindya De, and Rocco Servedio.
Testing noisy linear function for sparsity [arXiv, 20 minutes talk on youtube]
ACM Symposium on Theory of Computing (STOC) 2020.
Xue Chen and Anindya De.
Reconstruction under outliers for Fourier-sparse functions [arXiv]
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.
Xue Chen and Eric Price.
Estimating the Frequency of a Clustered Signal [arXiv]
International Colloquium on Automata, Languages and Programming (ICALP) 2019.
Xue Chen, Daniel M. Kane, Eric Price and Zhao Song.
Fourier-sparse Interpolation without a frequency gap [arXiv]
Symposium on Foundations of Computer Science (FOCS) 2016.
Foundations of Machine Learning
Xue Chen and Michał Dereziński
Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence [arXiv]
Conference on Learning Theory (COLT) 2021.
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan.
Adversarially Robust Low Dimensional Representations [arXiv]
Conference on Learning Theory (COLT) 2021.
Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan.
Estimating Principal Components under Adversarial Perturbations [arXiv]
Conference on Learning Theory (COLT) 2020.
Xue Chen and Eric Price.
Active Regression via Linear-sample Sparsification [arXiv, Eric's 45 mins talk at Simons]
Conference on Learning Theory (COLT) 2019.
Randomized Algorithms and Pseudorandomness
Dongrun Cai, Xue Chen, Pan Peng
Effective Resistances in Non-Expander Graphs [arXiv]
European Symposium on Algorithms (ESA) 2023
Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang
Improved Decoding of Expander Codes [arXiv]
Transaction of Information Theory 2023 & ITCS 2022
Xue Chen and David Zuckerman.
Existence of Simple Extractors [eccc]
Manuscript.
Xue Chen.
Derandomized Balanced Allocation [arXiv]
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.
Xue Chen and Yuan Zhou.
Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints [arXiv]
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.
Xue Chen.
Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders [arXiv]
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
Other writings
My Ph.D. dissertation: Using and Saving Randomness
On the Approximation Ratio of k-Lookahead Auction.
Xue Chen, Guangda Hu, Pinyan Lu, Lei Wang.
In WINE 2011.
A Better Upper Bound on Weights of Exact Threshold Functions.
Xue Chen, Guangda Hu, Xiaoming Sun.
In TAMC 2011.
The Complexity of Word Circuits.
Xue Chen, Guangda Hu, Xiaoming Sun.
In COCOON 2010.