research
∙
04/29/2023
Spectral clustering in the Gaussian mixture block model
Gaussian mixture block models are distributions over graphs that strive ...
share
research
∙
10/01/2022
Local and global expansion in random geometric graphs
Consider a random geometric 2-dimensional simplicial complex X sampled a...
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
∙
03/05/2022
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
We give a spectral algorithm for decomposing overcomplete order-4 tensor...
research
∙
11/22/2021
Testing thresholds for high-dimensional sparse random geometric graphs
In the random geometric graph model 𝖦𝖾𝗈_d(n,p), we identify each of our ...
research
∙
08/02/2021
The SDP value of random 2CSPs
We consider a very wide class of models for sparse random Boolean 2CSPs;...
research
∙
06/22/2021
Robust Regression Revisited: Acceleration and Improved Estimation Rates
We study fast algorithms for statistical regression problems under the s...
research
∙
02/17/2021
Non-asymptotic approximations of neural networks by Gaussian processes
We study the extent to which wide neural networks may be approximated by...
research
∙
11/11/2020
The Strongish Planted Clique Hypothesis and Its Consequences
We formulate a new hardness assumption, the Strongish Planted Clique Hyp...
research
∙
09/13/2020
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Researchers currently use a number of approaches to predict and substant...
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/17/2020
Playing Unique Games on Certified Small-Set Expanders
We give an algorithm for solving unique games (UG) instances whose const...
research
∙
11/23/2019
Subexponential LPs Approximate Max-Cut
We show that for every ε > 0, the degree-n^ε Sherali-Adams linear progra...
research
∙
12/24/2018
Sherali--Adams Strikes Back
Let G be any n-vertex graph whose random walk matrix has its nontrivial ...
research
∙
09/04/2018
SOS lower bounds with hard constraints: think global, act local
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficie...
research
∙
07/30/2018
High-dimensional estimation via sum-of-squares proofs
Estimation is the computational task of recovering a hidden parameter x ...
research
∙
05/07/2018
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
We give a quasipolynomial time algorithm for the graph matching problem ...
research
∙
04/14/2018
The threshold for SDP-refutation of random regular NAE-3SAT
Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has th...
research
∙
11/08/2017
Computing exact minimum cuts without knowing the graph
We give query-efficient algorithms for the global min-cut and the s-t cu...
research
∙
10/13/2017
The power of sum-of-squares for detecting hidden structures
We study planted problems---finding hidden structures in random noisy in...
research
∙
06/27/2017
Fast and robust tensor decomposition with applications to dictionary learning
We develop fast spectral algorithms for tensor decomposition that match ...
research
∙
12/08/2015
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
We consider two problems that arise in machine learning applications: th...
research
∙
06/09/2015