No Free Lunch in Data Privacy

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. 

This talk critically analyzes 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. I will 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.
I will 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 also describe 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, and conclude with directions for future research in data privacy
and big-data management.