TIME: 1:30 -- 2:30 pm, Tuesday, March 3, 2009

PLACE: CSE 503

SPEAKER: Frank McSherry, Microsoft Silicon Valley

TITLE: Differentially Private Approximation Algorithms

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 [self contained] talk, we will start with the definition of
differential privacy, and motivate its applications in statistical
settings. We then transport the definition to the vertex cover
problem, where some set of edges must each be covered by a
vertex. Treating the set of edges as sensitive (the presence or
absence of each edge should not be disclosed) we show a factor two
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.

Time permitting, we will survey several other approximation problems
and algorithms, including Min-Cut, Set Cover, k-Median, and CPPP,
without going into the details of the analyses.

This work is joint with Anupam Gupta, Katrina Ligett, Aaron Roth (all
at CMU) and Kunal Talwar (at MSR-SVC)

*: you'll see; it's a surprise!