The Complexity of Differential Privacy

By Salil P. Vadhan. 2017

378 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics, Privacy & Security, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “Similar to the traditional add/remove notion [71], Definition 1.”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “In central DP, the smallest possible estimation error for histograms is known to be Θ(min( log(1/δ)ε , logB ε , n)) (e.g., Section 7.1 in Vadhan (2017)).”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “In contrast, the definitions of [10, 62] and our definition measures the privacy of the entire transcript of an agent.”
Distributed Differential Privacy via Shuffling (2018, neutral): “[31]).”
Marginal Release Under Local Differential Privacy (2017, background): “It has been a topic of inquiry for diverse research communities including theory [35], data management [25], machine learning [33], and systems/programming languages [27].”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, methodology): “Note that this setting cannot be implemented using sampling without replacement since under the remove/add relation we cannot a priori guarantee that the input dataset will have at least size m because the size of the dataset must be kept private [Vadhan, 2017].”
Locally Differentially Private Frequent Itemset Mining (2018, background): “In the centralized settings, many DP algorithms have been proposed (see [17], [35] for theoretical treatments and [24] in a more practical perspective).”
Differentially Private Assouad, Fano, and Le Cam (2020, background): “Theorem 2 (ε-DP Fano’s inequality) can also be seen as a probabilistic generalization of the classic packing lower bound (Vadhan, 2017).”
Private Mean Estimation of Heavy-Tailed Distributions (2020, neutral): “Part 3 holds due to [BNS16, Vad17].”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, methodology): “[38, 55] provide methods to prove lower bounds on DP algorithms via packing.”
CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy (2018, background): “In the centralized settings, many DP algorithms have been proposed (see [15, 35] for theoretical treatments and [24] in a more practical perspective).”