Seminar • Algorithms and Complexity • Differentially Private Approximate Histograms using the Misra-Gries SketchExport this event to calendar

Wednesday, March 15, 2023 — 3:00 PM to 4:00 PM EDT

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.

Location 
DC - William G. Davis Computer Research Centre
DC 3317
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (98)
    1. April (21)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)