11 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…
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…