31 citations · 123 across the 9 of their papers we have counts for
6 papers · 1 filter
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Matthew Brennan, Guy Bresler, Samuel B. Hopkins +2
Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach…
Reducibility and Statistical-Computational Gaps from Secret Leakage
Matthew Brennan, Guy Bresler
Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science and statistical physics. While there has been succe…
Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
Matthew Brennan, Guy Bresler
This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computatio…
The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
Enric Boix-Adserà, Matthew Brennan, Guy Bresler
We consider the problem of counting -cliques in -uniform Erdos-Renyi hypergraphs with edge density , and show that its fine-grained average-case complexity can…
Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
Matthew Brennan, Guy Bresler
In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been drive…
Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
Matthew Brennan, Guy Bresler, Wasim Huleihel
The prototypical high-dimensional statistics problem entails finding a structured signal in noise. Many of these problems exhibit an intriguing phenomenon: the amount of data neede…