Please note: This seminar will take place in DC 3317.
Christian
Janos
Lebeda,
PhD
candidate
Basic
Algorithms
Research
Copenhagen
Algorithms
Group,
IT
University
of
Copenhagen
Estimating the histogram of a dataset is a fundamental task in differential privacy. Privacy is typically achieved by first computing the histogram and then independently adding noise to each entry. However, this approach assumes that we can compute the histogram exactly. This is not always possible such as in the data stream model where memory is very limited. In the non-private setting, we can approximate the histogram of a stream of elements with optimal worst-case guarantees using the Misra-Gries sketch. Chan, Li, Shi, and Xu [PETS 2012] first introduced an algorithm for releasing a Misra-Gries sketch under differential privacy, but the magnitude of the noise required to achieve privacy scales linearly in the size of the sketch.
In this talk, I will present a new algorithm for differentially private Misra-Gries sketches. I first introduce relevant techniques from differential privacy and the data stream model. I then present a new observation about the structure of Misra-Gries sketches. We utilize this structure to achieve differential privacy by adding noise almost identical to the non-streaming setting.
This is joint work with Jakub Tětek.