research
∙
06/30/2023
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique
Planted Dense Subgraph (PDS) problem is a prototypical problem with a co...
share
research
∙
05/17/2023
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
We aim to understand the extent to which the noise distribution in a pla...
research
∙
05/08/2023
Random Algebraic Graphs and Their Convergence to Erdos-Renyi
A random algebraic graph is defined by a group G with a uniform distribu...
research
∙
08/28/2022
Metastable Mixing of Markov Chains: Efficiently Sampling Low Temperature Exponential Random Graphs
In this paper we consider the problem of sampling from the low-temperatu...
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 ...
research
∙
04/13/2022
Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata
Given a matrix A and vector b with polynomial entries in d real variable...
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
∙
06/07/2021
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
We consider the problem of learning a tree-structured Ising model from d...
research
∙
06/03/2021
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
Let Φ be a uniformly random k-SAT formula with n variables and m clauses...
research
∙
03/29/2021
The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures
This paper studies the problem of estimating the means ±θ_*∈ℝ^d of a sym...
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
∙
06/16/2020
Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms
We study the problem of least squares linear regression where the data-p...
research
∙
06/07/2020
Learning Restricted Boltzmann Machines with Few Latent Variables
Restricted Boltzmann Machines (RBMs) are a common family of undirected g...
research
∙
06/07/2020
Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
We prove sharp dimension-free representation results for neural networks...
research
∙
05/16/2020
Reducibility and Statistical-Computational Gaps from Secret Leakage
Inference problems with conjectured statistical-computational gaps are u...
research
∙
02/01/2020
A Corrective View of Neural Networks: Representation, Memorization and Learning
We develop a corrective mechanism for neural network approximation: the ...
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
∙
11/25/2018
Sparse PCA from Sparse Linear Regression
Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression ...
research
∙
06/19/2018
Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
The prototypical high-dimensional statistics problem entails finding a s...
research
∙
05/25/2018
Learning Restricted Boltzmann Machines via Influence Maximization
Graphical models are a rich language for describing high-dimensional dis...
research
∙
05/08/2018
Information Storage in the Stochastic Ising Model
Most information systems store data by modifying the local state of matt...
research
∙
02/17/2018
Optimal Single Sample Tests for Structured versus Unstructured Network Data
We study the problem of testing, using only a single sample, between mea...
research
∙
12/15/2017
Stein's Method for Stationary Distributions of Markov Chains and Application to Ising Models
We develop a new technique, based on Stein's method, for comparing two s...
research
∙
11/06/2017
Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering
We consider an online model for recommendation systems, with each user b...
research
∙
04/22/2016
Learning a Tree-Structured Ising Model in Order to Make Predictions
We study the problem of learning a tree graphical model from samples suc...
research
∙
12/03/2014
Structure learning of antiferromagnetic Ising models
In this paper we investigate the computational complexity of learning th...
research
∙
11/22/2014
Efficiently learning Ising models on arbitrary graphs
We consider the problem of reconstructing the graph underlying an Ising ...
research
∙
10/31/2014
A Latent Source Model for Online Collaborative Filtering
Despite the prevalence of collaborative filtering in recommendation syst...
research
∙
10/28/2014
Learning graphical models from the Glauber dynamics
In this paper we consider the problem of learning undirected graphical m...
research
∙
09/12/2014