78 citations · 436 across the 33 of their papers we have counts for
41 papers
From Weak to Strong Testing in Gaussian Models
Ansh Nagda, Alexander S. Wein
We study the computational complexity of hypothesis testing in the spiked Wigner model, a prototypical model for detecting low-rank structure in a large random matrix. Below the "B…
Beyond Frequency Marching: Orbit Recovery in Dihedral and Projected Multireference Alignment
Tait Weicht, Alexander S. Wein
Multireference alignment (MRA) is the task of recovering a hidden "signal" vector, given many noisy copies that have been cyclically shifted by unknown offsets. This task belongs t…
Statistical inference of a ranked community in a directed graph
Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein +1
We study the problem of detecting or recovering a planted ranked subgraph from a directed graph, an analog for directed graphs of the well-studied planted dense subgraph model. We…
Tensor cumulants for statistical inference on invariant distributions
Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
Many problems in high-dimensional statistics appear to have a statistical-computational gap: a range of values of the signal-to-noise ratio where inference is information-theoretic…
Information-Theoretic Thresholds for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth , representin…
Precise Error Rates for Computationally Efficient Testing
Ankur Moitra, Alexander S. Wein
We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye towards computational complexity, as the statistically optimal likelihood ratio test is o…
Detection of Dense Subhypergraphs by Low-Degree Polynomials
Abhishek Dhawan, Cheng Mao, Alexander S. Wein
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergr…
Is Planted Coloring Easier than Planted Clique?
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein +1
We study the computational complexity of two related problems: recovering a planted -coloring in , and finding efficiently verifiable witnesses of non--colorability…
Detection-Recovery Gap for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biolog…
Is it easier to count communities than find them?
Cynthia Rush, Fiona Skerman, Alexander S. Wein +1
Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting…
Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation
Andrea Montanari, Alexander S. Wein
We consider the problem of estimating an unknown parameter vector , given noisy observations ${\boldsymbol Y} = {\boldsymbol θ}{\boldsymbol θ}^{\to…
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein
Suppose we are given an -dimensional order-3 symmetric tensor that is the sum of random rank-1 terms. The problem of recovering the rank-1…
Near-optimal fitting of ellipsoids to random points
Aaron Potechin, Paxton Turner, Prayaag Venkat +1
Given independent standard Gaussian points in dimension , for what values of does there exist with high probability an origin-symmetric ellipsoid tha…
Statistical and Computational Phase Transitions in Group Testing
Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth +2
We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of poo…
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins +3
Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for su…
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…
Circuit Lower Bounds for the p-Spin Optimization Problem
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
We consider the problem of finding a near ground state of a -spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent w…
Optimal Spectral Recovery of a Planted Vector in a Subspace
Cheng Mao, Alexander S. Wein
Recovering a planted vector in an -dimensional random subspace of is a generic task related to many problems in machine learning and statistics, such as dicti…
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…