NeurIPS 2019poster62 citations
Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
Abstract
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.
BibTeX
@inproceedings{NEURIPS2019_955cb567,
author = {Ullman, Jonathan and Sealfon, Adam},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/955cb567b6e38f4c6b3f28cc857fc38c-Paper.pdf},
volume = {32},
year = {2019}
}