On Differentially Private Counting on Trees
- Kewen Wu, UC Berkeley
- Time: 2023-07-11 16:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
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.
To appear at ICALP'23. Joint work with Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi.
Biography
Kewen Wu is a third-year graduate student, advised by Prof. Avishay Tal, at the theory group of UC Berkeley. He received Bachelor's degree in Computer Sciences and Mathematics from Peking University. He is broadly interested in theoretical computer sciences and relatd fields, with recent focuses on provable quantum advantages and the analysis of Boolean functions.