1 citations · 1 across the 12 of their papers we have counts for
14 papers
Near-optimal node-private community estimation in polynomial-time
Laurentiu Marchis, Olga Klopp, Po-Ling Loh +1
In this paper, we resolve an open question of Klopp & Zadik (2026) by providing a high-probability polynomial-time, node-private algorithm which nearly matches the performance of t…
A Bayesian Proof and Interpretation of Talagrand's Majorizing Measure Theorem
Ilias Zadik
In this paper, we give a short Bayesian proof of Talagrand's celebrated majorizing-measure theorem (MMT). While the upper-bound direction of MMT follows relatively directly from st…
Node-Private Community Detection in Stochastic Block Models
Olga Klopp, Ilias Zadik
We study community detection in stochastic block models under pure node-level differential privacy, a stringent notion that protects the participation of an individual together wit…
Stable Algorithms Lower Bounds for Estimation
Xifan Yu, Ilias Zadik
In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a vers…
The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
Konstantinos Tsirkas, Leda Wang, Ilias Zadik
Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics litera…
Almost-Optimal Local-Search Methods for Sparse Tensor PCA
Max Lovig, Conor Sheehan, Konstantinos Tsirkas +1
Local-search methods are widely employed in statistical applications, yet interestingly, their theoretical foundations remain rather underexplored, compared to other classes of est…
An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
Siyu Chen, Theodor Misiakiewicz, Ilias Zadik +1
Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an…
The Fundamental Limits of Recovering Planted Subgraphs
Daniel Lee, Francisco Pernice, Amit Rajaraman +1
Given an arbitrary subgraph and , the planted subgraph model is defined as follows. A statistician observes the union a random copy of , together…
On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem
Maxwell Lovig, Ilias Zadik
The group testing problem is a canonical inference task where one seeks to identify infected individuals out of a population of people, based on the outcomes of group t…
On the Hardness of Learning One Hidden Layer Neural Networks
Shuchen Li, Ilias Zadik, Manolis Zampetakis
In this work, we consider the problem of learning one hidden layer ReLU neural networks with inputs from . We show that this learning problem is hard under standard c…
Low-degree Security of the Planted Random Subgraph Problem
Andrej Bogdanov, Chris Jones, Alon Rosen +1
The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs , where is an Erdos-Renyi random graph on $…
On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
Zongchen Chen, Conor Sheehan, Ilias Zadik
Over the last years, there has been a significant amount of work studying the power of specific classes of computationally efficient estimators for multiple statistical parametric…
Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
Xifan Yu, Ilias Zadik, Peiyuan Zhang
We study the computational limits of the following general hypothesis testing problem. Let H=H_n be an \emph{arbitrary} undirected graph on n vertices. We study the detection task…
Transfer Learning Beyond Bounded Density Ratios
Alkis Kalavasis, Ilias Zadik, Manolis Zampetakis
We study the fundamental problem of transfer learning where a learning algorithm collects data from some source distribution but needs to perform well with respect to a differe…