@article{Sealfon_Ullman_2021, title={Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy}, volume={11}, url={https://journalprivacyconfidentiality.org/index.php/jpc/article/view/745}, DOI={10.29012/jpc.745}, abstractNote={<p>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.</p>}, number={1}, journal={Journal of Privacy and Confidentiality}, author={Sealfon, Adam and Ullman, Jonathan}, year={2021}, month={Feb.} }