13 citations · 16 across the 3 of their papers we have counts for
6 papers
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…
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky +2
We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-cas…
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…
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…
A Gramian Description of the Degree 4 Generalized Elliptope
Afonso S. Bandeira, Dmitriy Kunisky
One of the most widely studied convex relaxations in combinatorial optimization is the relaxation of the cut polytope to the elliptope , which correspo…