Xin Yang
PhD Student
Allen School of Computer Science & Engineering
University of Washington

yx1992 at
Paul G. Allen Center for Computer Science & Engineering, Office 418


I am a sixth-year PhD student in Computer Science and Engineering at the University of Washington, advised by Paul Beame. My research insterest is in lower bounds and hardness results in computational complexity. I am also interested in theory in machine learning.


Number Balancing is as hard as Minkowski′s Theorem and Shortest Vector, Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, Xin Yang, IPCO 2017, Arxiv.

Canaries in the Network, Danyang Zhuo, Qiao Zhang, Xin Yang, Vincent Liu, HotNets 2016.

Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials, Paul Beame, Shayan Oveis Gharan, Xin Yang, COLT 2018, Arxiv.

On the Bias of Reed-Muller Codes over Odd Prime Fields, Paul Beame, Shayan Oveis Gharan, Xin Yang, SIAM Journal on Discrete Mathematics 34 (2), 1232-1247, Arxiv.

Near optimal algorithm for approximating John′s Ellipsoid, Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang, COLT 2019, Arxiv.

Total Least Squares Regression in Input Sparsity Time, Huian Diao, Zhao Song, David Woodruff, Xin Yang, NeurIPS 2019, Arxiv.

Sketching Transformed Matrices with Applications to Natural Language Processing, Yingyu Liang, Zhao Song, Mengdi Wang, Lin Yang, Xin Yang, AISTATS 2020.