Xin Lyu

xinlyu (at) berkeley (dot) edu

634 Soda Hall, Berkeley, CA

I am a first-year Ph.D. student in the Theory Group at UC Berkeley, 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.


Manuscripts

Several ongoing projects in progress. Stay tuned!

Publications

On the Robustness of CountSketch to Adaptive Inputs [arXiv]
Edith Cohen, Xin Lyu, Jelani Nelson, Tamas Sarlos, Moshe Shechner, Uri Stemmer
To appear in ICML 2022

Improved Pseudorandom Generators for AC0 Circuits [pdf] [ECCC]
Xin Lyu
To appear in CCC 2022

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.