Monthly Center Meeting, September 18
Schedule:
10:00 – 10:30 —- PI Meeting
10:30 – 12:00 —- Guy Rothblum (See abstract below)
12:00 Lunch is served
1:45 – 2:00 — Announcements.
2:00 – 2:25 — Troy Lee short talk.
2:25 – 2:50 —- Robert Tarjan short talk.
Abstract for Guy Rothblum:
On the Computational Complexity of Privacy-Preserving Data Analysis
In this talk we will consider privacy-preserving data analysis in the
setting in which a trusted and trustworthy curator, having obtained a
data set containing sensitive information, releases to the public a
“sanitization” of the data set. The goal is for the sanitization to
both protect the privacy of individual contributors of data and offer
aggregate statistical utility to a data analyst.
We will survey some of the recent progress in this field through the
lens of computational complexity. In particular, we will study a
polynomial-time sanitizer due to Dwork and Nissim [CRYPTO 2004], and
an exponential-time sanitize due to Blum, Ligett and Roth, which
allows much richer statistical analysis than was previously possible
[STOC 2008]. Focusing on this computational complexity gap, we will
present both a more efficient sanitizer for rich data analysis, and
matching cryptographic hardness results from joint work with Dwork,
Naor, Reingold and Vadhan [STOC 2009].