research
∙
06/29/2022
Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs
In the anisotropic random geometric graph model, vertices correspond to ...
share
research
∙
08/24/2021
The staircase property: How hierarchical structure can guide deep learning
This paper identifies a structural property of data distributions that e...
research
∙
03/25/2021
De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions
A recent line of work has studied the relationship between the Wishart m...
research
∙
09/13/2020
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Researchers currently use a number of approaches to predict and substant...
research
∙
05/16/2020
Reducibility and Statistical-Computational Gaps from Secret Leakage
Inference problems with conjectured statistical-computational gaps are u...
research
∙
10/30/2019
Phase Transitions for Detecting Latent Geometry in Random Graphs
Random graphs with latent geometric structure are popular models of soci...
research
∙
08/08/2019
Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
This paper develops several average-case reduction techniques to show ne...
research
∙
03/19/2019
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
The complexity of clique problems on Erdos-Renyi random graphs has becom...
research
∙
02/20/2019
Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
In the past decade, sparse principal component analysis has emerged as a...
research
∙
02/19/2019
Universality of Computational Lower Bounds for Submatrix Detection
In the general submatrix detection problem, the task is to detect the pr...
research
∙
06/19/2018