Place
and Time: Wednesday, April 15th, 2009, Piece Hall 100F, 29 Oxford Street
Refreshments
at 2:30pm, talk at 2:45
We consider the problem of
designing approximation algorithms for discrete optimization problems over
private data sets, in the framework of differential privacy (which formalizes
the idea of protecting the privacy of individual input elements). Our results
show that for several commonly studied combinatorial optimization problems, it
is possible to release approximately optimal solutions while preserving
differential privacy; this is true even in cases where it is impossible under
cryptographic definitions of privacy to release even approximations to the
*value* of the optimal solution.
For example, in the private vertex cover problem, a set of edges must each be
covered by a vertex, without disclosing the presence or absence of any particular
edge. We show an efficient, differentially-private 2-approximation to the
value, and a factor (2 + 16/epsilon)-approximate solution (where epsilon is the
differential privacy parameter, controlling the amount of information
disclosure). We also present a simple lower bound arguing that an
Omega(1/epsilon) factor dependence is natural and necessary.
We will also discuss a variety of other combinatorial problems, and implications
of this work for mechanism design in submodular maximization problems.
Much of this work was done while the speaker was visiting Microsoft Research.
This work is joint with Anupam Gupta and Aaron Roth (both at Carnegie Mellon),
and Frank McSherry and Kunal Talwar (both at Microsoft Research).