License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.66
URN: urn:nbn:de:0030-drops-181186
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18118/
Ghazi, Badih ;
Kamath, Pritish ;
Kumar, Ravi ;
Manurangsi, Pasin ;
Wu, Kewen
On Differentially Private Counting on Trees
Abstract
We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a new error measure for this problem by considering a combination of multiplicative and additive approximation to the query results. We examine known mechanisms in differential privacy (DP) and prove their optimality, under this measure, in the pure-DP setting. In the approximate-DP setting, we design new algorithms achieving significant improvements over known ones.
BibTeX - Entry
@InProceedings{ghazi_et_al:LIPIcs.ICALP.2023.66,
author = {Ghazi, Badih and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin and Wu, Kewen},
title = {{On Differentially Private Counting on Trees}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {66:1--66:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18118},
URN = {urn:nbn:de:0030-drops-181186},
doi = {10.4230/LIPIcs.ICALP.2023.66},
annote = {Keywords: Differential Privacy, Algorithms, Trees, Hierarchies}
}
Keywords: |
|
Differential Privacy, Algorithms, Trees, Hierarchies |
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
05.07.2023 |