Eastern Great Lakes Theory Workshop Talk

Differentially Private Approximation Algorithms

Katrina Ligett, Cornell University

Saturday, October 3, 2:30-3:30pm

ABSTRACT

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.

In this talk, we'll focus on the private vertex cover problem, where 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.

To appear, SODA 2010. Much of this work was done while the speaker was visiting Microsoft Research - Silicon Valley. This work is joint with Anupam Gupta and Aaron Roth (both at Carnegie Mellon), and Frank McSherry and Kunal Talwar (both at Microsoft Research - SVC).

Slides

Speaker Bio

Katrina Ligett is a postdoctoral researcher in the computer science department at Cornell University. She received her PhD from Carnegie Mellon University in summer 2009, under the supervision of Avrim Blum. Her research interests include algorithmic game theory, learning theory, and data privacy.

< Schedule < EaGL-II homepage