[talks] M Hardt preFPO

[Melissa Lawson]

Moritz Hardt will present his preFPO on Thursday March 24 at 10:30 AM in Room 402.  
The members of his committee are;  Boaz Barak (advisor); Sanjeev Arora and Rocco 
Servedio (Columbia), readers; Moses Charikar and Rob Schapire, nonreaders.  Everyone 
is invited to attend his talk.  His abstract follows below.
---------------------------------------------

 Algorithmic techniques for privacy-preserving data analysis

We address the problem of privacy-preserving analysis of sensitive data.
Specifically we are interested in algorithms that satisfy the rigorous privacy
standard called differential privacy.

In the most basic setting of differential privacy we wish to respond to a
number of statistical queries on a data set posed by an (untrusted) data
analyst. As differential privacy forces us to give noisy answers, the basic
goal is to maximize the accuracy with which we answer each query while
maintaining differential privacy. Our results are the following:

- We first relate this problem to certain well-studied questions in
 high-dimensional geometry. Assuming the truth of a deep conjecture about
convex bodies, we design a new differentially private algorithm with optimal
accuracy so long as the number of queries is smaller than the size of the data
set and the queries are asked all at once.

- We next develop a privacy-preserving multiplicative weights framework which
 we use to give an algorithm in the case where the number of queries may be
significantly larger than the size of the data set and the queries may be
asked interactively. The accuracy of our algorithm is optimal in its
dependence on the database size.

- We then focus on a notable special case of statistical queries called
 Boolean conjunctions (aka contingency tables) that are of particular
importance from a statistical point of view. Neither of the aforementioned
algorithms has a polynomial runtime in this setting. We give the first
polynomial time algorithm for answering all Boolean conjunctions with a
non-trivial accuracy guarantee while satisfying differential privacy. Our result
is based on a new learning algorithm for submodular functions.

This talk is based on joint works with Anupam Gupta, Aaron Roth, Guy Rothblum,
Kunal Talwar and Jon Ullman.