The complexity of computing the optimal composition of differential privacy

DOI10.4086/TOC.2018.V014A008zbMATH Open1395.94305OpenAlexW2810915514MaRDI QIDQ4568112FDOQ4568112

Authors: Jack Murtagh, Salil Vadhan 

Publication date: 15 June 2018

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

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

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

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)

Cites Work

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

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)