13 citations · 40 across the 6 of their papers we have counts for
15 papers
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Ilias Zadik, Min Jae Song, Alexander S. Wein +1
Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canoni…
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}\…
Optimal Low-Degree Hardness of Maximum Independent Set
Alexander S. Wein
We study the algorithmic task of finding a large independent set in a sparse Erdős-Rényi random graph with vertices and average degree . The maximum independent set is known…
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…
Free Energy Wells and Overlap Gap Property in Sparse PCA
Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime, where the inference task is possible yet no polynomial-time algorithm is known to…
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…