2015/07/11 by Jack Murtagh, Murtagh, Jack, Salil Vadhan +1 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1507.03113
openalex publication_date 2015/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the study of differential privacy, composition theorems (starting with the\noriginal paper of Dwork, McSherry, Nissim, and Smith (TCC'06)) bound the\ndegradation of privacy when composing several differentially private\nalgorithms. Kairouz, Oh, and Viswanath (ICML'15) showed how to compute the\noptimal bound for composing k arbitrary (\ε,\δ)-differentially\nprivate algorithms. We characterize the optimal composition for the more\ngeneral case of k arbitrary\n(\ε1,\δ1),\…,(\εk,\δk)-differentially\nprivate algorithms where the privacy parameters may differ for each algorithm\nin the composition. We show that computing the optimal composition in general\nis #P-complete. Since computing optimal composition exactly is infeasible\n(unless FP= #P), we give an approximation algorithm that computes the\ncomposition to arbitrary accuracy in polynomial time. The algorithm is a\nmodification of Dyer's dynamic programming approach to approximately counting\nsolutions to knapsack problems (STOC'03).\n