摘要：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
(ε,δ)-differentially private algorithms. We characterize the optimal composition for the
more general case of k arbitrary (ε1,δ1),...,(εk,δ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).
