78 citations · 436 across the 33 of their papers we have counts for
9 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}\…
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…
Computational Barriers to Estimation from Low-Degree Polynomials
Tselil Schramm, Alexander S. Wein
One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data. A growing body of work studies low-d…
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…
Computationally efficient sparse clustering
Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretic…
Counterexamples to the Low-Degree Conjecture
Justin Holmgren, Alexander S. Wein
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", whic…
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Two concrete problems we consider are (a) optimizing the Hamil…