research
∙
07/03/2023
Fitting an ellipsoid to a quadratic number of random points
We consider the problem (P) of fitting n standard Gaussian random vector...
share
research
∙
02/27/2023
Injectivity of ReLU networks: perspectives from statistical physics
When can the input of a ReLU neural network be inferred from its output?...
research
∙
09/05/2022
On free energy barriers in Gaussian priors and failure of MCMC for high-dimensional unimodal distributions
We exhibit examples of high-dimensional unimodal posterior distributions...
research
∙
06/17/2022
A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture
In this expository note, we discuss an early partial coloring result of ...
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
∙
02/02/2021
Community Detection with a Subsampled Semidefinite Program
Semidefinite programming is an important tool to tackle several problems...
research
∙
02/01/2021
Group Testing in the High Dilution Regime
Non-adaptive group testing refers to the problem of inferring a sparse s...
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
∙
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
∙
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
∙
08/15/2019
Experimental performance of graph neural networks on random instances of max-cut
This note explores the applicability of unsupervised machine learning te...
research
∙
07/26/2019
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
We show that, if W∈R^N × N_sym is drawn from the gaussian orthogonal ens...
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
∙
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
∙
07/08/2018
Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
We study the problem of community detection in a random hypergraph model...
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
∙
06/22/2017
A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks
Many inverse problems are formulated as optimization problems over certa...
research
∙
12/22/2016
Statistical limits of spiked tensor models
We study the statistical limits of both detecting and estimating a rank-...
research
∙
10/17/2016
A polynomial-time relaxation of the Gromov-Hausdorff distance
The Gromov-Hausdorff distance provides a metric on the set of isometry c...
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
∙
07/08/2015
Multisection in the Stochastic Block Model using Semidefinite Programming
We consider the problem of identifying underlying community-like structu...
research
∙
04/10/2014