Xue Chen

Postdoc Fellow at Northwestern University

Email: <myfirstname>chencs AT gmail DOT com

OR <myfirstname>DOT chen1 AT northwestern DOT edu

Research interest: Randomized Algorithms and Pseudorandomness.

Specifically, fast Fourier transform, learning theory and optimization, sublinear algorithms, design of hash families and pseudorandom generators.

I am a postdoc in the theory group of Northwestern University. Previously, I obtained my Ph.D. in the University of Texas at Austin, fortunately advised by Professor David Zuckerman. Prior to that, I received my B.S. from the Yao class in Tsinghua University. Here is my CV .

Publications

Fourier transform and Sparse recovery

Reconstruction under outliers for Fourier-sparse functions [arXiv]

Manuscript.

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

In the Conference on Learning Theory (COLT) 2019.

Estimating the Frequency of a Clustered Signal [arXiv]

In the 46th International Colloquium on Automata, Languages and Programming (ICALP) 2019.

Fourier-sparse Interpolation without a frequency gap [arXiv, long slides]

In the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016).

Randomized Algorithms and Pseudorandomness

  • Xue Chen.

Derandomized Balanced Allocation [arXiv, short slides]

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

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

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

  • Xue Chen.

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

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

Other writings

Xue Chen and David Zuckerman.

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.