Faster Algorithms for Privately Releasing Marginals

DSpace/Manakin Repository

Faster Algorithms for Privately Releasing Marginals

Citable link to this page


Title: Faster Algorithms for Privately Releasing Marginals
Author: Thaler, Justin R; Ullman, Jonathan Robert; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Thaler, Justin, Jonathan Ullman, and Salil Vadhan. 2012. "Faster Algorithms for Privately Releasing Marginals." Lecture Notes in Computer Science 7391: 810-821. Presented at 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012. Also appears in Automata, Languages, and Programming. Springer-Verlag. doi:10.1007/978-3-642-31594-7_68.
Full Text & Related Files:
Abstract: We study the problem of releasing k-way marginals of a database D ∈ {0,1}d)n, while preserving differential privacy. The an- swer to a k-way marginal query is the fraction of D’s records x ∈ {0, 1}d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses of a dataset, and de- signing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf. Barak et. al., PODS ’07). We give an algorithm that runs in time dO( k) and releases a private summary capable of answering any k-way marginal query with at most ±.01 error on every query as long as n ≥ dO( k). To our knowledge, ours is the first algorithm capable of privately releasing marginal queries with non-trivial worst-case accuracy guarantees in time substantially smaller than the number of k-way marginal queries, which is dΘ(k) (for k ≪ d).
Published Version: doi:10.1007/978-3-642-31594-7_68
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search