Our weekly seminar series welcomes Aleksandar (Sasho) Nikolov, assistant professor in the Department of Computer Science at the University of Toronto and faculty fellow at the Schwartz Reisman Institute. Nikolov’s work focuses on the application of geometric tools to the theory of private data analysis, discrepancy theory (differential privacy).
Talk title
“How to analyze sensitive data: Differential privacy and factoring your queries.”
Abstract
How can we analyze data about people while protecting the privacy of the personal, sensitive information contained in the data? Can we do so, and also extract useful aggregate information from the data? Pinning down precisely what these questions mean is itself a significant conceptual challenge. While it may seem that aggregate information is “safe” from a personal privacy perspective, we know that sophisticated attacks can reconstruct the information of most individuals in a data set provided even approximate answers to aggregate questions (queries). In response to such attacks, Dwork, McSherry, Nissim, and Smith developed the notion of differential privacy as a way to define what it means for a data analysis procedure to protect privacy. Differential privacy has become a popular framework for thinking about data privacy questions, and differentially private data analysis methods are being used by several large companies (Google, Microsoft, Facebook, and Apple among them), and also by official statistics agencies (most notably the US Census Bureau for the 2020 Decennial Census).
In this talk, I will start by describing some of the pitfalls of naive approaches to private data analysis, as well as the ideas behind the reconstruction attacks referred to above. I will then introduce differential privacy and give intuition about how differentially private algorithms protect sensitive information. I will end by describing a method for answering questions of the type “how many people satisfy a given property?” based on factoring such questions into ones that are easier to answer. Such factorization mechanisms are deployed in practice, e.g., by the Census Bureau, and have many nice theoretical properties as well, some of them studied in recent work with Edmonds and Ullman.
Recommended readings
A. Cohen, S. Nikolov, Z. Schutzman, J. Ullman, “Theory of Reconstruction Attacks” and “Reconstruction Attacks in Practice.”
A. Wood et. al., “Differential Privacy: A Primer for a Non-technical Audience.” Vanderbilt Journal of Entertainment & Technology Law 21, no. 1 (2018): 209-275.
J.M. Abowd et. al., “The Modernization of Statistical Disclosure Limitation at the U.S. Census Bureau,” working paper.
A. Edmonds, A. Nikolov, J. Ullman, “The Power of Factorization Mechanisms in Local and Central Differential Privacy,” Proceedings of the 2020 Symposium on the Theory of Computing (STOC 2020).
About Aleksandar Nikolov
Aleksandar (Sasho) Nikolov is an assistant professor in the Department of Computer Science at the University of Toronto and faculty fellow at the Schwartz Reisman Institute. Nikolov’s work focuses on the application of geometric tools to the theory of private data analysis, discrepancy theory (differential privacy).
Nikolov completed his PhD at the Department of Computer Science at Rutgers University and is currently Canada Research Chair in Algorithms and Private Data Analysis at U of T. Before completing his PhD, Nikolov was a postdoctoral fellow with the Theory Group at Microsoft Research in Redmond, Washington.
About the SRI Seminar Series
The SRI Seminar Series brings together the Schwartz Reisman community and beyond for a robust exchange of ideas that advance scholarship at the intersection of technology and society. Seminars are led by a leading or emerging scholar and feature extensive discussion.
Each week, a featured speaker will present for 45 minutes, followed by 45 minutes of discussion. Registered attendees will be emailed a Zoom link approximately one hour before the event begins. The event will be recorded and posted online.
Aleksandar Nikolov