354 citations · 806 across the 36 of their papers we have counts for
7 papers · 1 filter
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique
Guy Bresler, Tianze Jiang
Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as…
Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs
Matthew Brennan, Guy Bresler, Brice Huang
In the anisotropic random geometric graph model, vertices correspond to points drawn from a high-dimensional Gaussian distribution and two vertices are connected if their distance…
The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures
Nir Weinberger, Guy Bresler
This paper studies the problem of estimating the means of a symmetric two-component Gaussian mixture …
Universality of Computational Lower Bounds for Submatrix Detection
Matthew Brennan, Guy Bresler, Wasim Huleihel
In the general submatrix detection problem, the task is to detect the presence of a small submatrix with entries sampled from a distribution in an $n \ti…
Sparse PCA from Sparse Linear Regression
Guy Bresler, Sung Min Park, Madalina Persu
Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR) have a wide range of applications and have attracted a tremendous amount of attention in the last two…
Optimal Single Sample Tests for Structured versus Unstructured Network Data
Guy Bresler, Dheeraj Nagaraj
We study the problem of testing, using only a single sample, between mean field distributions (like Curie-Weiss, Erdős-Rényi) and structured Gibbs distributions (like Ising model o…