Xue Chen

Assistant Professor

Department of Computer Science

George Mason University

Email: <myfirstname>chencs AT gmail DOT com

OR <myfirstname>chen AT gmu DOT edu


Algorithms for big data --- sparse recovery and fast Fourier transform; foundations of machine learning; derandomization and pseudorandomness.

Bio: I am 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 Yao Class at Tsinghua University.


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, long slides]

Symposium on Foundations of Computer Science (FOCS) 2016.

Foundations of Machine Learning

Estimating Principal Components under Adversarial Perturbations [arXiv]

Conference on Learning Theory (COLT) 2020.

Adversarially Robust Low Dimensional Representations [arXiv]


Active Regression via Linear-sample Sparsification [arXiv, long slides]

Conference on Learning Theory (COLT) 2019.

Pseudorandomness and Derandomization

Existence of Simple Extractors [eccc, long slides]


  • Xue Chen.

Derandomized Balanced Allocation [arXiv, short slides]

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

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

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

  • Xue Chen.

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

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

Other writings

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.