research
∙
03/21/2023
Algorithmic Threshold for Multi-Species Spherical Spin Glasses
We study efficient optimization of the Hamiltonians of multi-species sph...
share
research
∙
06/29/2022
Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs
In the anisotropic random geometric graph model, vertices correspond to ...
research
∙
06/10/2022
Tight Bounds for State Tomography with Incoherent Measurements
We consider the classic question of state tomography: given copies of an...
research
∙
04/14/2022
Tight Bounds for Quantum State Certification with Incoherent Measurements
We consider the problem of quantum state certification, where we are giv...
research
∙
10/15/2021
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
We study the problem of algorithmically optimizing the Hamiltonian H_N o...
research
∙
06/03/2021
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
Let Φ be a uniformly random k-SAT formula with n variables and m clauses...
research
∙
03/25/2021