  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 fraction of $D$'s records $x \in \{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 '07).
  We give an algorithm that runs in time $d^{O(\sqrt{k})}$ and releases a
private summary capable of answering any $k$-way marginal query with at most
$\pm .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 $k$-way marginal queries, which is $d^{\Theta(k)}$
(for $k \ll d$).

Data Structures and Algorithms