Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds
2026
Read Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15943.txt.
Introduction
Marchis and three colleagues study community recovery in stochastic block models under node differential privacy, where algorithms must stay stable when one node's links change. Naive private methods force the privacy parameter to grow fast for consistent estimation. Their new methods sample from an exponential mechanism with a Lipschitz extension and build smooth projections onto bounded-degree graphs. All run in polynomial time, and the authors also prove lower bounds on how fast the privacy parameter must grow.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 279882 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15943