Xin Lyu

xinlyu (at) berkeley (dot) edu

634 Soda Hall, Berkeley, CA

I am a third-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!


The Cost of Parallelizing Boosting [pdf available soon]
Xin Lyu, Hongxun Wu, Junzhao Yang
To appear at SODA 2024

The Target-Charging Technique for Privacy Analysis Across Interaction Computations [arXiv]
Edith Cohen, Xin Lyu
To appear at NeurIPS 2023

Tight Time-Space Lower Bounds for Constant-Pass Learning [arXiv]
Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
To appear at FOCS 2023

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting [ECCC]
Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu, William Hoza,
To appear at FOCS 2023

New PRGs for Unbounded-width/Adaptive-order Read-Once Branching Programs [DROPS]
Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu
ICALP 2023

Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization [arXiv]
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
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.