The Complexity of Computing the Optimal Composition of Differential Privacy

by Jack Murtagh and Salil Vadhan

Theory of Computing, Volume 14(8), pp. 1-35, 2018

Bibliography with links to cited articles

[1]   Hai Brenner and Kobbi Nissim: Impossibility of differentially private universally optimal mechanisms. SIAM J. Comput., 43(5):1513–1540, 2014. Preliminary version in FOCS’10. [doi:10.1137/110846671, arXiv:1008.0256]

[2]   Mark Bun and Thomas Steinke: Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proc. 14th Theory of Cryptography Conf. (TCC’16), pp. 635–658. Springer, 2016. [doi:10.1007/978-3-662-53641-4_24, arXiv:1605.02065]

[3]   Mercè Crosas: The dataverse network®;: An open-source application for sharing, discovering and preserving data. D-Lib Magazine, 17(1/2), 2011. [doi:10.1045/january2011-crosas]

[4]   Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor: Our data, ourselves: Privacy via distributed noise generation. In Proc. 25th Int. Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT’06), pp. 486–503. Springer, 2006. [doi:10.1007/11761679_29]

[5]   Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith: Calibrating noise to sensitivity in private data analysis. J. Privacy and Confidentiality, 7(3):17–51, 2016. Preliminary version in TCC’06. Available at journal’s webpage.

[6]   Cynthia Dwork and Aaron Roth: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. [doi:10.1561/0400000042]

[7]   Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan: Boosting and differential privacy. In Proc. 51st FOCS, pp. 51–60. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.12]

[8]   Martin E. Dyer: Approximate counting by dynamic programming. In Proc. 35th STOC, pp. 693–699. ACM Press, 2003. [doi:10.1145/780542.780643]

[9]   Matthias Ehrgott: Approximation algorithms for combinatorial multicriteria optimization problems. Internat. Trans. Operational Res., 7(1):5–31, 2000. [doi:10.1111/j.1475-3995.2000.tb00182.x]

[10]   Marco Gaboardi, James Honaker, Gary King, Jack Murtagh, Kobbi Nissim, Jonathan Ullman, and Salil P. Vadhan: PSI (Ψ  ): A private data sharing interface. Harvard University Privacy Tools Project, 2016. [arXiv:1609.04340]

[11]   Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan: Universally utility-maximizing privacy mechanisms. SIAM J. Comput., 41(6):1673–1693, 2012. Preliminary version in STOC’09. [doi:10.1137/09076828X, arXiv:0811.2841]

[12]   Peter Kairouz, Sewoong Oh, and Pramod Viswanath: The composition theorem for differential privacy. IEEE Trans. Inform. Theory, 63(6):4037–4049, 2017. Preliminary version in ICML’15. [doi:10.1109/TIT.2017.2685505, arXiv:1311.0776]

[13]   Gary King: An introduction to the dataverse network as an infrastructure for data sharing. Sociological Methods & Research, 36(2):173–199, 2007. [doi:10.1177/0049124107306660]

[14]   Jack Murtagh and Salil P. Vadhan: The complexity of computing the optimal composition of differential privacy. In Proc. 14th Theory of Cryptography Conf. (TCC’16), pp. 157–175. Springer, 2016. [doi:10.1007/978-3-662-49096-9_7, arXiv:1507.03113v2]

[15]   Stanley L. Warner: Randomized response: A survey technique for eliminating evasive answer bias. J. Amer. Stat. Assoc., 60(309):63–69, 1965. [doi:10.1080/01621459.1965.10480775]