CIS Seminar - Adam Smith
Speaker: Adam Smith , Penn State Universitiy
Date: February 29 2008
Time: 10:30AM to 12:00PM
Location: 32--G449
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL:
A recent line of work investigates the possibility of publishing "anonymized" statistical summaries that reveal global properties of a database of sensitive information (think of data from a census, social network, or medical study), without revealing any information specific to the individuals in the database.
In this talk, we ask what types of *learning* problems can be solved (and their results, published) while preserving rigorous notions of privacy. Learning problems form an important category of computational tasks that includes many of the computations applied to large, real-life datasets.
Roughly, our study corresponds to asking: what learning problems can be solved by algorithms that do not depend heavily on any single input?
Some highlights:
a) Ignoring computation time, but retaining the restrictions of polynomial sample complexity and a polynomially-sized output, the class of solvable classification problems (roughly, Valiant's "PAC" model) is the same with and without the constraint of preserving privacy.
b) There are polynomial-time *private* learning algorithms for the PARITY problem.Together with earlier results on "statistical query" (SQ) learning, this implies that all commonly studied learning classes have efficient private learners.
c) The power of "local" privacy-preserving publication mechanisms is equivalent to SQ. Local mechanisms, in which each contributing individual anonymizes his/her own data, generalize "randomized response" and other techniques. The data mining community has studied local mechanisms extensively. Our results imply that these popular mechanisms are strictly less powerful than the more general model used above for learning parity.
Based on joint work with Shiva Kasivswanathan, Homin Lee, Kobbi Nissim and Sofya Raskhodnikova.
*The talk will be self-contained.* However, attendees may also be interested in a talk to be given by Sofya Raskhodnikova (on different, but related, results) on Thursday, 2/ 28 in the algorithms seminar.
See other events that are part of Cryptography and Information Security Seminars 2007/2008
See other events happening in February 2008
