1 citations · 1 across the 1 of their papers we have counts for
5 papers
Analyzing XOR-Forrelation through stochastic calculus
Xinyu Wu
In this note we present a simplified analysis of the quantum and classical complexity of the -XOR Forrelation problem (introduced in the paper of Girish, Raz and Zhan) by a stoc…
The SDP value of random 2CSPs
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm +1
We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~. For each model , we identify…
Explicit near-fully X-Ramanujan graphs
Ryan O'Donnell, Xinyu Wu
Let be a self-adjoint noncommutative polynomial, with coefficients from , in the indeterminates (co…
A stochastic calculus approach to the oracle separation of BQP and PH
Xinyu Wu
After presentations of Raz and Tal's oracle separation of BQP and PH result, several people (e.g. Ryan O'Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified…
A log-Sobolev inequality for the multislice, with applications
Yuval Filmus, Ryan O'Donnell, Xinyu Wu
Let satisfy and let denote the "multislice" of all strings in having exactly coordinates eq…