Alexander S. Wein

research

∙ 04/17/2023

Detection of Dense Subhypergraphs by Low-Degree Polynomials

Detection of a planted dense subgraph in a random graph is a fundamental...

0 Abhishek Dhawan, et al. ∙

research

∙ 03/01/2023

Is Planted Coloring Easier than Planted Clique?

We study the computational complexity of two related problems: recoverin...

0 Pravesh K. Kothari, et al. ∙

research

∙ 02/13/2023

Detection-Recovery Gap for Planted Dense Cycles

Planted dense cycles are a type of latent structure that appears in many...

0 Cheng Mao, et al. ∙

research

∙ 12/21/2022

Is it easier to count communities than find them?

Random graph models with community structure have been studied extensive...

0 Cynthia Rush, et al. ∙

research

∙ 12/14/2022

Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation

We consider the problem of estimating an unknown parameter vector θ∈ℝ^n,...

0 Andrea Montanari, et al. ∙

research

∙ 11/10/2022

Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials

Suppose we are given an n-dimensional order-3 symmetric tensor T ∈ (ℝ^n)...

0 Alexander S. Wein, et al. ∙

research

∙ 08/19/2022

Near-optimal fitting of ellipsoids to random points

Given independent standard Gaussian points v_1, …, v_n in dimension d, f...

0 Prayaag Venkat, et al. ∙

research

∙ 06/15/2022

Statistical and Computational Phase Transitions in Group Testing

We study the group testing problem where the goal is to identify a set o...

0 Amin Coja-Oghlan, et al. ∙

research

∙ 05/19/2022

The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

Many high-dimensional statistical inference problems are believed to pos...

0 Afonso S. Bandeira, et al. ∙

research

∙ 12/07/2021

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

Clustering is a fundamental primitive in unsupervised learning which giv...

0 Ilias Zadik, et al. ∙

research

∙ 09/03/2021

Circuit Lower Bounds for the p-Spin Optimization Problem

We consider the problem of finding a near ground state of a p-spin model...

0 David Gamarnik, et al. ∙

research

∙ 05/31/2021

Optimal Spectral Recovery of a Planted Vector in a Subspace

Recovering a planted vector v in an n-dimensional random subspace of ℝ^N...

0 Cheng Mao, et al. ∙

research

∙ 12/03/2020

Average-Case Integrality Gap for Non-Negative Principal Component Analysis

Montanari and Richard (2015) asked whether a natural semidefinite progra...

0 Afonso S. Bandeira, et al. ∙

research

∙ 10/13/2020

Optimal Low-Degree Hardness of Maximum Independent Set

We study the algorithmic task of finding a large independent set in a sp...

0 Alexander S. Wein, et al. ∙

research

∙ 08/27/2020

Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

We study the problem of efficiently refuting the k-colorability of a gra...

0 Afonso S. Bandeira, et al. ∙

research

∙ 08/05/2020

Computational Barriers to Estimation from Low-Degree Polynomials

One fundamental goal of high-dimensional statistics is to detect or reco...

0 Tselil Schramm, et al. ∙

research

∙ 06/18/2020

Free Energy Wells and Overlap Gap Property in Sparse PCA

We study a variant of the sparse PCA (principal component analysis) prob...

0 Gérard Ben Arous, et al. ∙

research

∙ 05/22/2020

The Average-Case Time Complexity of Certifying the Restricted Isometry Property

In compressed sensing, the restricted isometry property (RIP) on M × N s...

0 Yunzi Ding, et al. ∙

research

∙ 05/21/2020

Computationally efficient sparse clustering

We study statistical and computational limits of clustering when the mea...

0 Matthias Löffler, et al. ∙

research

∙ 04/25/2020

Low-Degree Hardness of Random Optimization Problems

We consider the problem of finding nearly optimal solutions of optimizat...

0 David Gamarnik, et al. ∙

research

∙ 04/17/2020

Counterexamples to the Low-Degree Conjecture

A conjecture of Hopkins (2018) posits that for certain high-dimensional ...

0 Justin Holmgren, et al. ∙

research

∙ 07/26/2019

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

These notes survey and explore an emerging method, which we call the low...

0 Dmitriy Kunisky, et al. ∙

research

∙ 07/26/2019

Subexponential-Time Algorithms for Sparse PCA

We study the computational cost of recovering a unit-norm sparse princip...

0 Yunzi Ding, et al. ∙

research

∙ 04/08/2019

The Kikuchi Hierarchy and Tensor PCA

For the tensor PCA (principal component analysis) problem, we propose a ...

0 Alexander S. Wein, et al. ∙

research

∙ 02/19/2019

Computational Hardness of Certifying Bounds on Constrained PCA Problems

Given a random n × n symmetric matrix W drawn from the Gaussian orthogo...

0 Afonso S. Bandeira, et al. ∙

research

∙ 11/02/2018

Spectral Methods from Tensor Networks

A tensor network is a diagram that specifies a way to "multiply" a colle...

0 Ankur Moitra, et al. ∙

research

∙ 07/02/2018

Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models

A central problem of random matrix theory is to understand the eigenvalu...

0 Amelia Perry, et al. ∙

research

∙ 03/29/2018

Notes on computational-to-statistical gaps: predictions using statistical physics

In these notes we describe heuristics to predict computational-to-statis...

0 Afonso S. Bandeira, et al. ∙

research

∙ 12/29/2017

Estimation under group actions: recovering orbits from invariants

Motivated by geometric problems in signal processing, computer vision, a...

0 Afonso S. Bandeira, et al. ∙

research

∙ 12/22/2016

Statistical limits of spiked tensor models

We study the statistical limits of both detecting and estimating a rank-...

0 Amelia Perry, et al. ∙

research

∙ 10/14/2016

Message-passing algorithms for synchronization problems over compact groups

Various alignment problems arising in cryo-electron microscopy, communit...

0 Amelia Perry, et al. ∙

research

∙ 09/19/2016

Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization

A central problem of random matrix theory is to understand the eigenvalu...

0 Amelia Perry, et al. ∙

research

∙ 11/04/2015

How Robust are Reconstruction Thresholds for Community Detection?

The stochastic block model is one of the oldest and most ubiquitous mode...

0 Ankur Moitra, et al. ∙

Alexander S. Wein

Featured Co-authors