Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations

Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar

Consider a database of $n$ people, each represented by a bit-string of length $d$ corresponding to the setting of $d$ binary attributes. A $k$-way marginal query is specified by a…