MSc Thesis Presentation - Emily Gong
Name: Zehui Gong
Date: Thu, 2024/08/29
Time: 11:00 am
Location: ICCS 238
Supervisor: Nick Harvey
Title: Streaming algorithms with differential privacy guarantee
Abstract:
In this thesis, we present two algorithms that solve the distinct element estimating problem (or cardinality estimating), and we show that both are differentially private.
The first algorithm uses a decision-based approach to estimate the number of distinct elements, achieving an accuracy within a factor of (1±γ)with a probability of 1−α. The algorithm has a space complexity of O(γ−3log1α log2n). We prove this algorithm is inherently differentially private. Additionally, we extend the algorithm to handle deletions with space complexityO(γ−3log1α log1γ log2n).
The second algorithm uses ideas from Johnson-Lindenstrauss Lemma and uses p-stable distribution instead of Gaussians. For small enough p = O(γ/log n), we can estimate distinct elements up to a factor of
(1±γ) with high probability. We prove upper and lower bounds for p-stable distribution using an infinite sum representation of its density. In addition, we show that if p ≤ 0.01, the algorithm is (ϵ,δ)-differentially private in the one-dimensional case, where ϵ=ln(11.46(1+p)) and δ=0.84.