13 citations · 19 across the 9 of their papers we have counts for
5 papers · 1 filter
Strong recovery of geometric planted matchings
Dmitriy Kunisky, Jonathan Niles-Weed
We study the problem of efficiently recovering the matching between an unlabelled collection of points in and a small random perturbation of those points. We con…
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Montanari and Richard (2015) asked whether a natural semidefinite programming (SDP) relaxation can effectively optimize over $\|\mathbf{x}\…
Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
Dmitriy Kunisky
We introduce a new method for building higher-degree sum-of-squares lower bounds over the hypercube from a given degree 2 lower bound. Our method const…
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…