The Complexity of Computing the Optimal Composition of Differential Privacy

DOI10.1007/978-3-662-49096-9_7zbMath1388.94074arXiv1507.03113OpenAlexW1465390462MaRDI QIDQ2796124

Jack Murtagh, Salil P. Vadhan

Publication date: 23 March 2016

Published in: Theory of Cryptography (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.03113

zbMATH Keywords

computational complexitycompositionapproximation algorithmsdifferential privacy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

Separating Computational and Statistical Differential Privacy in the Client-Server Model ⋮ Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds ⋮ Fingerprinting Codes and the Price of Approximate Differential Privacy ⋮ Unnamed Item ⋮ PAC privacy: automatic privacy measurement and control of data processing ⋮ Differential privacy: getting more for less ⋮ Concurrent composition of differential privacy ⋮ Asymmetric Distances for Approximate Differential Privacy ⋮ Unnamed Item ⋮ The Complexity of Differential Privacy ⋮ A Novel Adaptive Differential Privacy Algorithm for Empirical Risk Minimization

Uses Software

• Dataverse

Cites Work

• Unnamed Item
• Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
• The Algorithmic Foundations of Differential Privacy
• Approximate counting by dynamic programming
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• The Composition Theorem for Differential Privacy
• Theory of Cryptography

This page was built for publication: The Complexity of Computing the Optimal Composition of Differential Privacy