8 citations · 29 across the 13 of their papers we have counts for
10 papers · 1 filter
Sharp thresholds in inference of planted subgraphs
Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn +2
A major question in the study of the Erdős--Rényi random graph is to understand the probability that it contains a given subgraph. This study originated in classical work of Erdős…
Optimal Private Median Estimation under Minimal Distributional Assumptions
Christos Tzamos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Ilias Zadik
We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distr…
Group testing and local search: is there a computational-statistical gap?
Fotis Iliopoulos, Ilias Zadik
In this work we study the fundamental limits of approximate recovery in the context of group testing. One of the most well-known, theoretically optimal, and easy to implement testi…
The All-or-Nothing Phenomenon in Sparse Tensor PCA
Jonathan Niles-Weed, Ilias Zadik
We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive Gaussian noise, a model also known as sparse tensor PCA. We show that for Bernoulli an…
All-or-Nothing Phenomena: From Single-Letter to High Dimensions
Galen Reeves, Jiaming Xu, Ilias Zadik
We consider the linear regression problem of estimating a -dimensional vector from observations , where for a real-val…
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
David Gamarnik, Ilias Zadik
In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size is planted in an Erdos Renyi graph resulting i…