`xinyuwu AT cmu DOT edu`

I am a third-year PhD student in the Theory Group in the Computer Science Department at Carnegie Mellon University. I am fortunate to be advised by Pravesh Kothari and Ryan O'Donnell. I am broadly interested in theoretical computer science. Recently, I have been thinking about free probability, spectral graph theory, random graphs, and their applications in understanding average-case problems and quantum computing. My research is supported by a Microsoft Research Ada Lovelace Fellowship.

*Analyzing XOR-Forrelation through stochastic calculus* (pdf) (arXiv)

Xinyu Wu

Manuscript

*The SDP value of random 2CSPs* (pdf) (arXiv)

Amulya Musipatla,
Ryan O'Donnell,
Tselil Schramm,
Xinyu Wu

Manuscript

*Explicit near-fully X-Ramanujan graphs* (pdf) (arXiv)

Ryan O'Donnell,
Xinyu Wu

FOCS 2020

*Mycielski graphs and PR proofs* (pdf)

Emre Yolcu,
Xinyu Wu,
Marijn Heule

SAT 2020

**Best Student Paper**

*The nonlinear stability regime of the viscous Faraday wave problem* (pdf) (arXiv)

David Altizio,
Ian Tice,
Xinyu Wu,
Taisuke Yasuda

Quarterly of Applied Mathematics, 2019

*A log-Sobolev inequality for the multislice, with applications* (pdf) (arXiv)

Yuval Filmus,
Ryan O'Donnell,
Xinyu Wu

ITCS 2019

*A stochastic calculus approach to the oracle separation of BQP and PH* (pdf) (ECCC) (arXiv)

Xinyu Wu

*To appear,* Theory of Computing

*The uniform marginals lemma in "Query-to-communication lifting for BPP"* (pdf)

*Separations in computational complexity through stochastic calculus*

USC Probability and Statistics Seminar, October 2021 (video)

*Explicit near-fully X-Ramanujan graphs*

IAS CSDM Seminar, October 2020 (video)

HUJI Combinatorics Seminar; CMU Theory Lunch, July 2020 (video) (slides)

*Escaping small sets on the boolean cube and other domains*

CMU Theory Lunch, October 2018 (video) (slides)

*Query-to-communication lifting for BPP* (Göös, Pitassi, Watson 2017)

(with Ryan O'Donnell) CMU Theory Reading Group, April 2017 (video part 1) (part 2)