November 3, 2011 - Ashwin Machanavajjhala

Title: No Free Lunch in Data Privacy

Abstract:
Legal requirements and increase in public awareness due to egregious breaches of individual privacy have made data privacy an important field of research. Recent research, culminating in the development of a powerful notion called differential privacy, have transformed this field from a black art into a rigorous mathematical discipline.

In this talk, we critically analyze the trade-off between accuracy and privacy in the context of social advertising – recommending people, products or services to users based on their social neighborhood. We present a theoretical upper bound on the accuracy of performing recommendations that are solely based on a user's social network, for a given level of (differential) privacy of sensitive links in the social graph. We also show using real networks that good private social recommendations are feasible only for a small subset of the users in the social network or for a lenient setting of privacy parameters.

I will conclude the talk with some exciting new research about a no free lunch theorem, which argues that privacy tools (including differential privacy) cannot simultaneously guarantee utility as well as privacy for all types of data.