Faster Algorithms for Privately Releasing Marginals

Justin Thaler, Jonathan Ullman, Salil Vadhan

We study the problem of releasing $k$-way marginals of a database $D\in (\{0,1{\}}^d{)}^n$, while preserving differential privacy. The answer to a $k$-way marginal query is the fracti…