@conference {555471,
	title = {The Complexity of Computing the Optimal Composition of Differential Privacy},
	booktitle = {Theory of Cryptography Conference (TCC 2016)},
	volume = {14},
	year = {2018},
	pages = {1-35},
	publisher = {Theory of Computing (2018)},
	organization = {Theory of Computing (2018)},
	edition = {8},
	abstract = {In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC{\textquoteright}06)) bound the degradation of privacy when composing several differentially private algorithms. Kairouz, Oh, and Viswanath (ICML{\textquoteright}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),{\textellipsis},(ϵ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{\textquoteright}s dynamic programming approach to approximately counting solutions to knapsack problems (STOC{\textquoteright}03).},
	url = {http://theoryofcomputing.org/articles/v014a008/},
	author = {Jack Murtagh and Salil Vadhan}
}
