19 citations · 70 across the 39 of their papers we have counts for
6 papers · 1 filter
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}\…
Hypothesis testing with low-degree polynomials in the Morris class of exponential families
Dmitriy Kunisky
Analysis of low-degree polynomial algorithms is a powerful, newly-popular method for predicting computational thresholds in hypothesis testing problems. One limitation of current t…
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…
Linear Programming and Community Detection
Alberto Del Pia, Aida Khajavirad, Dmitriy Kunisky
The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic bl…
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1
In compressed sensing, the restricted isometry property (RIP) on sensing matrices (where ) guarantees efficient reconstruction of sparse vectors. A matrix has t…