Below are the details for the theory seminar talk on monday Nov. 1 
(2:30pm in room 261).

Title: Privacy Against Many Arbitrary Low-Sensitivity Queries
Speaker: Cynthia Dwork, Microsoft Research

We consider privacy-preserving data analysis, in which a trusted 
curator, holding an n-row database filled with personal information, is 
presented with a large set Q of queries about the database. The 
curator's task is to return relatively accurate responses to all 
queries, while simultaneously protecting the privacy of the individual 
database rows.  Our notion of privacy is differential privacy.

In a seminal paper Dinur and Nissim showed in that "overly accurate" 
answers to "too many" counting queries (``How many rows in the database 
satisfy Property~$P$?'')  destroys any hope of privacy, differential or 
otherwise.  Nonetheless, Dwork and Nissim were able to answer a slightly 
sub-linear number of counting queries with distortion o(n^{1/2}) -- an 
amount less than the sampling error -- while achieving what is now known 
as (epsilon,delta)-differential privacy.

The general question of trading accuracy for numbers of counting queries 
has been an active and exciting area of research, with some startling 
results.  Several factors come into play: are the queries known in 
advance?  What are the relationships between the size of the universe of 
database rows, the size of the database, and the number of queries?  To 
what extent does the curator retain state between successive queries?

In this talk we briefly review the definition of differential privacy, 
highlight a few results from the literature on counting queries, and 
then turn to the question of arbitrary "low sensitivity" queries -- that 
is, queries whose answers change by only a small amount with the 
addition or deletion of a single database row. We address these with an 
unorthodox application of boosting, a powerful learning technique 
typically applied to labeled data items, but in our case is applied to 
the queries themselves.

This is joint work with Guy Rothblum and Salil Vadhan.