Xin Lyu 吕欣 (original) (raw)

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.