@conference {634259,
	title = {Faster algorithms for privately releasing marginals},
	booktitle = {Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP {\textquoteleft}12), Lecture Notes on Computer Science},
	volume = {7391},
	year = {2012},
	pages = {810-821},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	abstract = {
	Version History:\&nbsp;Full version posted as\&nbsp;arXiv:1205.1758v2.



	We study the problem of releasing\&nbsp;k-way marginals\&nbsp;of a database\&nbsp;\(D\&nbsp;∈\&nbsp;({0,1}^d)^n\), while preserving differential privacy. The answer to a\&nbsp;\(k\)-way marginal query is the fraction of\&nbsp;\(D\){\textquoteright}s records\&nbsp;\(x\&nbsp;\in \{0,1\}^d\)\&nbsp;with a given value in each of a given set of up to\&nbsp;\(k\)\&nbsp;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\&nbsp;\(d^{O(\sqrt{K})}\)\&nbsp;and releases a private summary capable of answering any\&nbsp;\(k\)-way marginal query with at most\&nbsp;{\textpm}.01 error on every query as long as \(n \geq d^{O(\sqrt{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\&nbsp;k-way marginal queries, which is\&nbsp;\(d^{\Theta(k)}\)\&nbsp;(for\&nbsp;\(k\&nbsp;<<\&nbsp;d\)).

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-31594-7_68},
	author = {Justin Thaler and Jonathan Ullman and Salil Vadhan}
}
