Graph-based modelling of query sets for differential privacy
Ali İnan, Mehmet Emre Gürsoy, Emir Esmerdag, Yücel Saygın · 2016
Differential privacy has gained attention from the community as the mechanism for privacy protection. Significant effort has focused on its application to data analysis, where statistical queries are submitted in batch and answers to these queries are perturbed with noise. The magnitude of this noise depends on the privacy parameter ϵ and the sensitivity of the query set. However, computing the sensitivity is known to be NP-hard.