13 citations · 20 across the 29 of their papers we have counts for
4 papers · 1 filter
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensio…
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
Dmitriy Kunisky, Afonso S. Bandeira
We show that, if is drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares rela…
Computational Hardness of Certifying Bounds on Constrained PCA Problems
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Given a random symmetric matrix drawn from the Gaussian orthogonal ensemble (GOE), we consider the problem of certifying an upper bound on the maximum…
Sum-of-Squares Optimization and the Sparsity Structure of Equiangular Tight Frames
Afonso S. Bandeira, Dmitriy Kunisky
Equiangular tight frames (ETFs) may be used to construct examples of feasible points for semidefinite programs arising in sum-of-squares (SOS) optimization. We show how generalizin…