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, Tamas Sarlos and Uri Stemmer.
Several ongoing projects in progress. Stay tuned!
Composition Theorems for Interactive Differential Privacy
To appear in NeurIPS 2022
(Note: See also this independent and concurrent work by Vadhan and Zhang.)
Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness
On the Robustness of CountSketch to Adaptive Inputs
Improved Pseudorandom Generators for AC^0 Circuits
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]
Igor C. Oliveira
Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma
[pdf] [ECCC] [My virtual talk at STOC]
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
[ECCC] [My virtual talk at FOCS]
When I am not doing research, I play Genshin Impact, chess, strategic board games (Through the Ages, Twilight Struggle, Civilization VI, etc.) for fun.