Xin Lyu

xinlyu (at) berkeley (dot) edu

634 Soda Hall, Berkeley, CA

I am a second-year Ph.D. student in the Theory Group at UC Berkeley, where I am fortunate to be advised by Avishay Tal and Jelani Nelson.

My research interests lie in theoretical computer science in general. Recently, I have been thinking about problems in pseudorandomness, computational complexity and differential privacy. I am more than happy to hear comments/questions about my research. Feel free to reach out!

Previously, I did my undergrad at the Institute for Interdisciplinary Information Sciences (aka. Yao Class) at Tsinghua University. During the Spring and Summer of 2020, I was fortunate to visit MIT and work on complexity theory, under the supervision of Prof. Ryan Williams. In Summer 2022, I had a happy internship at Google Research (Mountain View), where I worked closely with Edith Cohen, Jelani Nelson, Tamás Sarlós and Uri Stemmer.


Several ongoing projects in progress. Stay tuned!


Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization [arXiv]
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
To appear in STOC 2023

Generalized Private Selection and Testing with High Confidence [arXiv]
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
ITCS 2023

Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness [arXiv]
Xin Lyu, Weihao Zhu
SODA 2023

Composition Theorems for Interactive Differential Privacy [arXiv]
Xin Lyu
NeurIPS 2023
(Note: See also this independent and concurrent work by Vadhan and Zhang.)

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness [ECCC]
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

On the Robustness of CountSketch to Adaptive Inputs [arXiv]
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer
ICML 2022

Improved Pseudorandom Generators for AC^0 Circuits [pdf] [ECCC]
Xin Lyu
CCC 2022 (co-winner of best student paper; invited to the ToC special issue)

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC^1 [pdf] [ECCC] [DROPS] [My virtual talk at ICALP]
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira
ICALP 2021

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma [pdf] [ECCC] [My virtual talk at STOC]
Lijie Chen, Xin Lyu
STOC 2021

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization [pdf] [ECCC] [My virtual talk at FOCS]
Lijie Chen, Xin Lyu, Ryan Williams
FOCS 2020

About Me

When I am not doing research, I play Genshin Impact, chess, strategic board games (Through the Ages, Twilight Struggle, Civilization VI, etc.) for fun.