Xue Chen

---

About Me

I am broadly interested in theoretical computer science. Specific areas include big data algorithms, learning theory and foundations of machine learning, complexity theory, randomized algorithms and pseudorandomness.

Currently I am a faculty member in the School of Computer Science and Technology of University of Science and Technology of China. Previously, I was a postdoc in the theory group of Northwestern University (in USA) and an assistant professor in George Mason University (in USA). Prior to that, I obtained my PhD in the University of Texas at Austin, under the supervision of David Zuckerman, and my bachelor degree from the Yao class of Tsinghua University.

Here is my CV.

---

Prospective Students

If you are interested in my projects or want to know more about my research, feel free to send me an email or drop by my office after 3pm.

---

Teaching

Fall 2019 Graduate Complexity at Northwestern University.

Fall 2020 Theory of Computation at George Mason University.

Spring 2021 Advanced Algorithms at George Mason University.

Fall 2021 Advanced Algorithms Design and Analysis at USTC.

Spring 2022 Concrete Math (graduate) at USTC.

Spring 2022 Introduction to Algorithm at USTC.

---

Publications (my google scholar)

Foundations of Machine Learning

• Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence [arXiv, videos in COLT]
  Xue Chen and Michal Derezinski
  In Conference on Learning Theory (COLT) 2021.
• Adversarially Robust Low Dimensional Representations [arXiv, videos in COLT]
  Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, and Aravindan Vijayaraghavan
  In Conference on Learning Theory (COLT) 2021.
• Estimating Principal Components under Adversarial Perturbations [arXiv, videos in COLT]
  Pranjal Awasthi, Xue Chen, and Aravindan Vijayaraghavan
  In Conference on Learning Theory (COLT) 2020.
• Active Regression via Linear-Sample Sparsification [arXiv, 45 mins talk by Eric at Simons]
  Xue Chen and Eric Price
  In Conference on Learning Theory (COLT) 2019.

Big Data Algorithms

• Testing noisy linear functions for sparsity [arXiv, 20 mins talk, 1 hour talk by Rocco at Simons]
  Xue Chen, Anindya De, and Rocco A. Servedio
  In ACM Symposium on Theory of Computing (STOC) 2020.
• Reconstruction under outliers for Fourier-sparse functions [arXiv]
  Xue Chen and Anindya De
  In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.
• Estimating the Frequency of a Clustered Signal [arXiv]
  Xue Chen and Eric Price
  In the 46th International Colloquium on Automata, Languages and Programming (ICALP) 2019.
• Fourier-sparse Interpolation without a Frequency gap [arXiv, 30 mins talk by Eric at Banff Research]
  Xue Chen, Daniel M. Kane, Eric Price, and Zhao Song.
  In the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016).

Randomized Algorithms and Pseudorandomness

• Improved Decoding of Expander Codes [arXiv, 25 mins talk in ITCS]
  Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang
  Transaction on Information Theory 2023, perliminary version in the 13th Innovations in Theoretical Computer Science (ITCS) 2022.
• Derandomized Balanced Allocation [arXiv]
  Xue Chen
  In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.
• Existence of Simple Extractors [eccc]
  Xue Chen and David Zuckerman
  Manuscrip.
• Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints [arXiv]
  Xue Chen and Yuan Zhou
  In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.
• Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders [arXiv]
  Xue Chen
  In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.

Other Writings

• [My PhD thesis]
• On the Approximation Ratio of k-Lookahead Auction
  Xue Chen, Guangda Hu, Pinyan Lu, and Lei Wang
  In WINE 2011.
• A Better Upper Bound on Weights of Exact Threshold Functions.
  Xue Chen, Guangda Hu, and Xiaoming Sun
  In TAMC 2011.
• The Complexity of Word Circuits.
  Xue Chen, Guangda Hu, and Xiaoming Sun
  In COCOON 2011.