31 citations · 123 across the 9 of their papers we have counts for
13 papers
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 staircase property: How hierarchical structure can guide deep learning
Emmanuel Abbe, Enric Boix-Adsera, Matthew Brennan +2
This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the "staircase" property for functions over t…
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…
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…
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…
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…
Ramsey numbers of trees versus odd cycles
Matthew Brennan
Burr, Erdős, Faudree, Rousseau and Schelp initiated the study of Ramsey numbers of trees versus odd cycles, proving that for all odd and $n \ge 756…
Ramsey numbers of trees and unicyclic graphs versus fans
Matthew Brennan
The generalized Ramsey number is the smallest positive integer such that for any graph with vertices either contains as a subgraph or its complement $…