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

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE279882
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15943

Browse the full library · About the Tower of Babel