Fetching the paper…

Reading the bibliography…

2018

Private Algorithms Can Always Be Extended

Borgs, Christian, Chayes, Jennifer, Smith, Adam et al.

Original
PDF
Post on X

Understand

We consider the following fundamental question on $\epsilon$-differential privacy.

Consider an arbitrary $\epsilon$-differentially private algorithm defined on a subset of the input space.
Is it possible to extend it to an $\epsilon'$-differentially private algorithm on the whole input space for some $\epsilon'$ comparable with $\epsilon$? In this note we answer affirmatively this question for $\epsilon'=2\epsilon$.
Our result applies to every input metric space and space of possible outputs.

Private Algorithms Can Always Be Extended · Around

Built on

Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Differentially private data analysis of social networks via restricted sensitivity
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet · 2013
Earlier work this paper cites.
Recursive mechanism: towards node differential privacy and unrestricted joins
Shixi Chen and Shuigeng Zhou · 2013
Earlier work this paper cites.

Similar

Analyzing graphs with node-differential privacy
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2013
Cited alongside, same era.
Metric embeddings and lipschitz extensions, lecture notes
Assaf Naor · 2015
Cited alongside, same era.
Publishing graph degree distribution with node differential privacy
Wei-Yen Day, Ninghui Li, and Min Lyu · 2016
Cited alongside, same era.

Then

Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism
Sofya Raskhodnikova and Adam D. Smith · 2016
Later among the works it cites.
Revealing network structure confidentially: Improved rates for node-private graphon estimation
Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik · 2018
Closest in time.
Individual sensitivity preprocessing for data privacy
Original
Rachel Cummings and David Durfee · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…