The complexity of computing the optimal composition of differential privacy

DOI10.4086/TOC.2018.V014A008MaRDI QIDQ4568112zbMATH OpenOpenAlexFDO

Authors Jack Murtagh, Salil Vadhan

Publication date 15 June 2018

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2018.v014a008

zbMATH Keywords

approximation algorithmscomplexity theorycompositiondifferential 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)

Recommendations

• The complexity of computing the optimal composition of differential privacy
• Concurrent composition of differential privacy
• The algorithmic foundations of differential privacy
• Answering \(n^2+o(1)\) counting queries with differential privacy is hard
• Differentially private combinatorial optimization

Cites work

• Approximate counting by dynamic programming
• Impossibility of Differentially Private Universally Optimal Mechanisms
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Randomized response: a survey technique for eliminating evasive answer bias
• The Composition Theorem for Differential Privacy
• The algorithmic foundations of differential privacy
• The complexity of computing the optimal composition of differential privacy
• Universally utility-maximizing privacy mechanisms

Cited in

(3)

• Foundations of Differentially Oblivious Algorithms
• The complexity of computing the optimal composition of differential privacy
• Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs

This page was built for publication: The complexity of computing the optimal composition of differential privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568112)