Abstract: Differential privacy offers a mathematical framework for balancing two goals: obtaining useful information about sensitive data, and protecting individual-level privacy. Discovering the limitations of differential privacy yields insights as to what analyses are incompatible with privacy and why. These insights further aid the quest to discover optimal privacy-preserving algorithms. In this talk, Mark will give examples of how both follow from new understandings of the structure of differential privacy. He will first describe negative results for private data analysis via a connection to cryptographic objects called fingerprinting codes. These results show that an (asymptotically) optimal way to solve natural high-dimensional tasks is to decompose them into many simpler tasks. In the second part of the talk, he will discuss concentrated differential privacy, a framework which enables more accurate analyses by precisely capturing how simpler tasks compose.
Bio: Mark Bun is a postdoctoral researcher in the Theory of Computation Group at Princeton University, where he is hosted by Mark Zhandry. Before coming to Princeton, he completed my Ph.D. in computer science at Harvard University in November 2016, where he was very fortunate to have Salil Vadhan as his advisor. As an undergraduate, Mark studied math and computer science at the University of Washington.
He is broadly interested in theoretical computer science, including data privacy, computational complexity, cryptography, and the foundations of machine learning. My current research focuses on:
Using the methodologies of complexity theory to answer practically-motivated questions in algorithmic data privacy, and
Understanding the power of real polynomial approximations to Boolean functions and their applications in quantum computation, communication complexity, and learning theory.
A reception for attendees will be held at 3:30 in CS 150 (the back of the presentation room).