354 citations · 806 across the 36 of their papers we have counts for
5 papers · 1 filter
Phase Transitions for Detecting Latent Geometry in Random Graphs
Matthew Brennan, Guy Bresler, Dheeraj Nagaraj
Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These g…
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…
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…