21 citations · 58 across the 4 of their papers we have counts for
7 papers
De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions
Matthew Brennan, Guy Bresler, Brice Huang
A recent line of work has studied the relationship between the Wishart matrix , where has i.i.d. standard Gaussian entries, and the correspo…
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…
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…
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…