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...
share
research
∙
03/01/2023
Is Planted Coloring Easier than Planted Clique?
We study the computational complexity of two related problems: recoverin...
research
∙
02/13/2023
Detection-Recovery Gap for Planted Dense Cycles
Planted dense cycles are a type of latent structure that appears in many...
research
∙
12/21/2022
Is it easier to count communities than find them?
Random graph models with community structure have been studied extensive...
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,...
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)...
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...
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...
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...
research
∙
12/07/2021
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Clustering is a fundamental primitive in unsupervised learning which giv...
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...
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...
research
∙
12/03/2020
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Montanari and Richard (2015) asked whether a natural semidefinite progra...
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...
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...
research
∙
08/05/2020
Computational Barriers to Estimation from Low-Degree Polynomials
One fundamental goal of high-dimensional statistics is to detect or reco...
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...
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...
research
∙
05/21/2020
Computationally efficient sparse clustering
We study statistical and computational limits of clustering when the mea...
research
∙
04/25/2020
Low-Degree Hardness of Random Optimization Problems
We consider the problem of finding nearly optimal solutions of optimizat...
research
∙
04/17/2020
Counterexamples to the Low-Degree Conjecture
A conjecture of Hopkins (2018) posits that for certain high-dimensional ...
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...
research
∙
07/26/2019
Subexponential-Time Algorithms for Sparse PCA
We study the computational cost of recovering a unit-norm sparse princip...
research
∙
04/08/2019
The Kikuchi Hierarchy and Tensor PCA
For the tensor PCA (principal component analysis) problem, we propose a ...
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...
research
∙
11/02/2018
Spectral Methods from Tensor Networks
A tensor network is a diagram that specifies a way to "multiply" a colle...
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...
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...
research
∙
12/29/2017
Estimation under group actions: recovering orbits from invariants
Motivated by geometric problems in signal processing, computer vision, a...
research
∙
12/22/2016
Statistical limits of spiked tensor models
We study the statistical limits of both detecting and estimating a rank-...
research
∙
10/14/2016
Message-passing algorithms for synchronization problems over compact groups
Various alignment problems arising in cryo-electron microscopy, communit...
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...
research
∙
11/04/2015