Ashwin Machanavajjhala
Yahoo! Research
Computer Science Building, Room 151
Faculty Host: Gerome Miklau and Lisa Ballesteros, Mt. Holyoke College
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. An algorithm satisfying differential privacy guarantees that the distribution of its outputs changes very little with the addition or deletion of an individual's record in the data. Differential privacy has been successfully used to publish noisy (yet accurate) answers from statistical databases, where individual records have little or no correlation with others in the table.
In this talk we critically analyze the privacy protections offered by differential privacy on correlated data. Such correlated data arise naturally in social interaction data or in tabular data released along with exact statistics. First, we will describe the trade-off between accuracy of performing ``social recommendations'', or recommendations that are solely based on a user's social network, and the (differential) privacy of sensitive links in the social graph. We 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. Next, using examples of correlated data, we show that the use of differential privacy can lead to privacy breaches. We present a no-free-lunch theorem to argue that privacy tools like differential privacy, which do not make assumptions about how the data are generated, cannot simultaneously provide both privacy and utility. We propose a participation-based privacy model to overcome the weaknesses of differential privacy.
BIO:
Ashwin Machanavajjhala is a Research Scientist in the Knowledge Management group at Yahoo! Research. His primary research interests lie in the area of data management, with specific focus on information extraction, probabilistic reasoning and privacy on the web. Ashwin graduated with a Ph.D. from the Department of Computer Science, Cornell University. His thesis work on defining and enforcing privacy was awarded the 2009 ACM SIGMOD Jim Gray Dissertation Award Honorable Mention. He has also received an M.S. from Cornell University and a B.Tech in Computer Science and Engineering from the Indian Institute of Technology, Madras.