On the complexity of differentially private data release: efficient algorithms and hardness results

By Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan. 2009

520 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Detecting Violations of Differential Privacy (2018, background): “: queries to the database, ϵ0: privacy budget T : threshold, N : bound of outputting True’s ∆: sensitivity 1 function iSVT4(Q , T , ϵ0, ∆, N): 2 out ← [ ] 3 η1 ← Lap(2 ∗ ∆/ϵ0) 4 T̃ ← T + η1 5 count ← 0 6 foreach q in Q do 7 η2 ← Lap(2 ∗ N ∗ ∆/ϵ0) 8 if q + η2 ≥ T̃ then 9 // output numerical value ins”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “This sample complexity is also achieved by the sparse vector algorithm [20], [21, §3.”
Boosting and Differential Privacy (2010, methodology): “For the special case of counting queries we can use a base synopsis generator from [11], and obtain accuracy roughly √ n · log |Q| (improving on the bound of √ n · |Q|o(1)| from [11]) with a running time of poly(|Q|, |X |).”
Advanced Probabilistic Couplings for Differential Privacy (2016, neutral): “[20]; several refinements were proposed by Hardt and Rothblum [30], Roth and Roughgarden [44].”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “Dwork et al. (2009) more recently characterized when utility and privacy can be achieved by e cient non-interactive mechanisms.”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, background): “It has been demonstrated that differentially private analyses exist for a variety of tasks including the approximation of numerical functions (by adding carefully chosen random noise that conceals any single individual’s contribution) [11, 2, 22, 17], non-numerical analyses [20], datamining [2, 22],”
Preserving Statistical Validity in Adaptive Data Analysis (2014, methodology): “This result is based on the Sparse Vector technique [17, 20].”
Fingerprinting codes and the price of approximate differential privacy (2013, methodology): “[16], who used cryptographic“traitortracing schemes”to prove computational hardness results for differential privacy.”
Differentially private combinatorial optimization (2009, background): “, see [11, 8, 27, 6, 23, 15, 12], and see [9] for an excellent survey), that tries to capture the intuition of individual privacy.”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, neutral): “(the construction is not generally feasible [10,20,19]).”