Understand
In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC'06)) bound the degradation of privacy when composing several differentially private algorithms.
- Kairouz, Oh, and Viswanath (ICML'15) showed how to compute the optimal bound for composing $k$ arbitrary $(\epsilon,\delta)$-differentially private algorithms.
- We characterize the optimal composition for the more general case of $k$ arbitrary $(\epsilon_{1},\delta_{1}),\ldots,(\epsilon_{k},\delta_{k})$-differentially private algorithms where the privacy parameters may differ for each algorithm in the composition.
- We show that computing the optimal composition in general is $\#$P-complete.
Built on
[War65] Stanley L. Warner. Randomized Response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association
1965
Earlier work this paper cites.
[Ehr00] Matthias Ehrgott. Approximation algorithms for combinatorial multicriteria optimization problems. International Transactions in Operational Research
2000
Earlier work this paper cites.
[Dye03] Martin Dyer. Approximate counting by dynamic programming. Proceedings of the 35th annual ACM Symposium on Theory of Computing (STOC’13)
2003
Earlier work this paper cites.
[DKMMN06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: privacy via distributed noise generation. Advances in Cryptology-EUROCRYPT
2006
Earlier work this paper cites.
Similar
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis: Third Theory of Cryptography Conference (TCC’06)
2006
Cited alongside, same era.
[Kin07] Gary King. An introduction to the Dataverse Network as an infrastructure for data sharing. Sociological Methods & Research
2007
Cited alongside, same era.
[DRV10] Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10), 2010 51st Annual IEEE Symposium
2010
Cited alongside, same era.
Then
[Cro11] Mercè Crosas. The Dataverse Network®: an open-source application for sharing, discovering and preserving data. D-lib Magazine
2011
Later among the works it cites.
[DR13] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science
2013
Later among the works it cites.
[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The Composition Theorem for Differential Privacy. Proceedings of the 32nd International Conference on Machine Learning, (ICML’15)
2015
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…