Theory of Computing
-------------------
Title     : The Complexity of Computing the Optimal Composition of Differential Privacy
Authors   : Jack Murtagh and Salil Vadhan
Volume    : 14
Number    : 8
Pages     : 1-35
URL       : https://theoryofcomputing.org/articles/v014a008

Abstract
--------

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. Since computing
optimal composition exactly is infeasible (unless FP=#P), we give
an approximation algorithm that computes the composition to arbitrary
accuracy in polynomial time. The algorithm is a modification of Dyer's
dynamic programming approach to approximately counting solutions to
knapsack problems (STOC'03).

A conference version of this paper appeared in the
13th IACR Theory of Cryptography Conference (TCC 2016).