TY - JOUR
AU - Sealfon, Adam
AU - Ullman, Jonathan
PY - 2021/02/03
Y2 - 2024/11/06
TI - Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
JF - Journal of Privacy and Confidentiality
JA - JPC
VL - 11
IS - 1
SE - TPDP 2019
DO - 10.29012/jpc.745
UR - https://journalprivacyconfidentiality.org/index.php/jpc/article/view/745
SP -
AB - <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>
ER -