Iterative constructions and private data release

摘要: In this paper we study the problem of approximately releasing cut function a graph while preserving differential privacy, and give new algorithms (and analyses existing algorithms) in both interactive non-interactive settings. Our setting are achieved by revisiting differentially private, approximate answers to large number queries on database. We show that several for fall into same basic framework, based existence objects which call iterative database construction algorithms. generic framework (efficient) IDC rise private query release mechanisms. Our modular analysis simplifies tightens previous algorithms, leading improved bounds. then algorithm therefore mechanism) Frieze/Kannan low-rank matrix decomposition. This mechanism gives an improvement prior work range parameters where size is comparable data universe (such as all dense graphs). We also efficiently synthetic cuts with error O(|V|1.5). randomized response non-private implementation SDP-based, constant-factor approximation cut-norm due Alon Naor. Finally, reduction showing efficient, computing sufficiently accurate rank-1 approximations would lead efficient cuts. leave finding such our main open problem.