Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy

Main Article Content

Adam Sealfon
Jonathan Ullman


We give a simple, computationally efficient, and node-differentially-private algorithm for estimating the parameter of an Erdos-Renyi graph---that is, estimating p in a G(n,p)---with near-optimal accuracy. Our algorithm nearly matches the information-theoretically optimal exponential-time algorithm for the same problem due to Borgs et al. (FOCS 2018). More generally, we give an optimal, computationally efficient, private algorithm for estimating the edge-density of any graph whose degree distribution is concentrated in a small interval.

Article Details

How to Cite
Sealfon, Adam, and Jonathan Ullman. 2021. “Efficiently Estimating Erdos-Renyi Graphs With Node Differential Privacy”. Journal of Privacy and Confidentiality 11 (1). https://doi.org/10.29012/jpc.745.
TPDP 2019

Most read articles by the same author(s)