Speaker: Mark Bun
, Harvard University
Title: Differentially private release and learning of threshold functions
The line of work on differential privacy is aimed at enabling rich statistical analyses on data while provably protecting individual-level privacy. The last decade of research has shown that, at least in principle, a number of fundamental statistical tasks are compatible with differential privacy. However, privacy-preserving analyses often require additional complexity over their non-private counterparts: for instance, in terms of the number of data samples one needs to collect in order to get accurate results. In this talk, we will examine the price of privacy for several basic tasks involving one-dimensional threshold functions. We give the first non-trivial lower bounds on the sample complexity of performing these tasks with (approximate) differential privacy. Surprisingly, our techniques seem closely related to classic results in distributed computing, and bolster connections between privacy and combinatorics.
Joint work with Kobbi Nissim, Uri Stemmer, and Salil Vadhan.