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