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. 

Publications (my google scholar)
Fourier transform and Sparse recovery

Testing noisy linear function for sparsity [arXiv, 20 minutes talk on youtube]

ACM Symposium on Theory of Computing (STOC) 2020.

Reconstruction under outliers for Fourier-sparse functions [arXiv]

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

Estimating the Frequency of a Clustered Signal [arXiv]

International Colloquium on Automata, Languages and Programming (ICALP) 2019.

Fourier-sparse Interpolation without a frequency gap [arXiv]

Symposium on Foundations of Computer Science (FOCS) 2016.

Foundations of Machine Learning

Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence [arXiv]

Conference on Learning Theory (COLT) 2021.

Adversarially Robust Low Dimensional Representations [arXiv]

Conference on Learning Theory (COLT) 2021.

Estimating Principal Components under Adversarial Perturbations [arXiv]

Conference on Learning Theory (COLT) 2020.

Active Regression via Linear-sample Sparsification [arXiv, Eric's 45 mins talk at Simons]

Conference on Learning Theory (COLT) 2019.

Randomized Algorithms and Pseudorandomness

Effective Resistances in Non-Expander Graphs [arXiv]

European Symposium on Algorithms (ESA) 2023

Improved Decoding of Expander Codes [arXiv]

Transaction of Information Theory 2023 & ITCS 2022

Existence of Simple Extractors [eccc]

Manuscript.

Derandomized Balanced Allocation [arXiv]

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.

Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints [arXiv]

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.

Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders [arXiv]

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.

Other writings

Xue Chen, Guangda Hu, Pinyan Lu, Lei Wang.

In WINE 2011.

Xue Chen, Guangda Hu, Xiaoming Sun.

In TAMC 2011.

Xue Chen, Guangda Hu, Xiaoming Sun.

In COCOON 2010.