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.
Manuscripts
Several ongoing projects in progress. Stay tuned!
Publications
Õ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
RANDOM 2022
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.