ncts

A central paradigm in theoretical computer science is to reason about the space of all possible algorithms for any given problem. That is, we seek to identify an algorithm with the "best" possible performance, and then prove that no algorithm can perform better, no matter how cleverly it is designed. In this talk, I will illustrate how this paradigm has played a central role in the development of differential privacy, a mathematical framework for enabling the statistical analysis of privacy-sensitive datasets while ensuring that information specific to individual data subjects will not be leaked. In particular, we are using it to delineate the border between what is possible and what is impossible in differential privacy, and the effort has uncovered intriguing connections with several other topics in theoretical computer science an mathematics.