@conference {ThalerUlVa12,
	title = {Faster Algorithms for Privately Releasing Marginals},
	booktitle = {Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012},
	volume = {7391},
	year = {2012},
	month = {9-13 Jul.},
	publisher = {Springer},
	organization = {Springer},
	edition = {Lecture Notes in Computer Science},
	address = {Warwick, UK},
	abstract = {We study the problem of releasing k-way marginals of a database D ∈ ({0, 1} d ) n , while preserving differential privacy. The answer to a k-way marginal query is the fraction of D{\textquoteright}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 designing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf. Barak et. al., PODS {\textquoteright}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 {\textpm}.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).},
	url = {http://dx.doi.org/10.1007/978-3-642-31594-7_68},
	author = {Justin Thaler and Jonathan Ullman and Salil P. Vadhan}
}
