Timezone: »
Poster
Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
Jonathan Ullman · Adam Sealfon
Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #91
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.
Author Information
Jonathan Ullman (Northeastern University)
Adam Sealfon (UC Berkeley)
More from the Same Authors
-
2021 Spotlight: Covariance-Aware Private Mean Estimation Without Private Covariance Estimation »
Gavin Brown · Marco Gaboardi · Adam Smith · Jonathan Ullman · Lydia Zakynthinou -
2021 Poster: Covariance-Aware Private Mean Estimation Without Private Covariance Estimation »
Gavin Brown · Marco Gaboardi · Adam Smith · Jonathan Ullman · Lydia Zakynthinou -
2020 Poster: CoinPress: Practical Private Mean and Covariance Estimation »
Sourav Biswas · Yihe Dong · Gautam Kamath · Jonathan Ullman -
2020 Poster: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2020 Poster: Auditing Differentially Private Machine Learning: How Private is Private SGD? »
Matthew Jagielski · Jonathan Ullman · Alina Oprea -
2020 Spotlight: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2019 Poster: Differentially Private Algorithms for Learning Mixtures of Separated Gaussians »
Gautam Kamath · Or Sheffet · Vikrant Singhal · Jonathan Ullman -
2018 Poster: The Limits of Post-Selection Generalization »
Jonathan Ullman · Adam Smith · Kobbi Nissim · Uri Stemmer · Thomas Steinke -
2018 Poster: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2018 Spotlight: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2016 Poster: Privacy Odometers and Filters: Pay-as-you-Go Composition »
Ryan Rogers · Salil Vadhan · Aaron Roth · Jonathan Ullman