[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Mark Bun
Harvard University
http://people.seas.harvard.edu/~mbun/

Tuesday, February 9, 2016
Ryerson 251 @ 3 pm

Title: Differentially private release and learning of threshold functions

Abstract:
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 differential privacy. Surprisingly, our techniques are 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.

Host: Prof. Alexander Razborov

Refreshments will be served prior to the talk in Ryerson 255 @ 2:30 pm


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160122/b939d6f3/attachment-0001.htm