research
∙
02/28/2023
Sharp thresholds in inference of planted subgraphs
A major question in the study of the Erdős–Rényi random graph is to unde...
share
research
∙
09/22/2022
A second moment proof of the spread lemma
This note concerns a well-known result which we term the “spread lemma,”...
research
∙
09/07/2022
On the Second Kahn–Kalai Conjecture
For any given graph H, we are interested in p_crit(H), the minimal p suc...
research
∙
08/15/2022
Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions
The last few years have seen a surge of work on high dimensional statist...
research
∙
06/15/2022
Statistical and Computational Phase Transitions in Group Testing
We study the group testing problem where the goal is to identify a set o...
research
∙
05/19/2022
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Many high-dimensional statistical inference problems are believed to pos...
research
∙
04/05/2022
Almost-Linear Planted Cliques Elude the Metropolis Process
A seminal work of Jerrum (1992) showed that large cliques elude the Metr...
research
∙
12/07/2021
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Clustering is a fundamental primitive in unsupervised learning which giv...
research
∙
06/20/2021
On the Cryptographic Hardness of Learning Single Periodic Neurons
We show a simple reduction which demonstrates the cryptographic hardness...
research
∙
03/02/2021
Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
We consider the problem of finding a two-layer neural network with sigmo...
research
∙
02/24/2021
It was "all" for "nothing": sharp phase transitions for noiseless discrete channels
We establish a phase transition known as the "all-or-nothing" phenomenon...
research
∙
11/12/2020
Optimal Private Median Estimation under Minimal Distributional Assumptions
We study the fundamental task of estimating the median of an underlying ...
research
∙
11/10/2020
Group testing and local search: is there a computational-statistical gap?
In this work we study the fundamental limits of approximate recovery in ...
research
∙
07/22/2020
The All-or-Nothing Phenomenon in Sparse Tensor PCA
We study the statistical problem of estimating a rank-one sparse tensor ...
research
∙
06/18/2020
Free Energy Wells and Overlap Gap Property in Sparse PCA
We study a variant of the sparse PCA (principal component analysis) prob...
research
∙
03/23/2020
Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
In the context of neural network models, overparametrization refers to t...
research
∙
12/30/2019
All-or-Nothing Phenomena: From Single-Letter to High Dimensions
We consider the linear regression problem of estimating a p-dimensional ...
research
∙
12/03/2019
Stationary Points of Shallow Neural Networks with Quadratic Activation Function
We consider the problem of learning shallow neural networks with quadrat...
research
∙
10/24/2019
Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
We focus on the high-dimensional linear regression problem, where the al...
research
∙
04/15/2019
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
In this paper we study the computational-statistical gap of the planted ...
research
∙
03/12/2019
The All-or-Nothing Phenomenon in Sparse Linear Regression
We study the problem of recovering a hidden binary k-sparse p-dimensiona...
research
∙
03/10/2019
A simple bound on the BER of the MAP decoder for massive MIMO systems
The deployment of massive MIMO systems has revived much of the interest ...
research
∙
10/30/2018
Private Algorithms Can Always Be Extended
We consider the following fundamental question on ϵ-differential privacy...
research
∙
10/30/2018
Private Algorithms Can be Always Extended
We consider the following fundamental question on ϵ-differential privacy...
research
∙
10/04/2018
Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation
Motivated by growing concerns over ensuring privacy on social networks, ...
research
∙
03/18/2018
High Dimensional Linear Regression using Lattice Basis Reduction
We consider a high dimensional linear regression problem where the goal ...
research
∙
11/14/2017
Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
We consider a sparse high dimensional regression model where the goal is...
research
∙
11/01/2017
Orthogonal Machine Learning: Power and Limitations
Double machine learning provides √(n)-consistent estimates of parameters...
research
∙
01/16/2017