2022
Order-Invariant Cardinality Estimators Are Differentially Private
NeurIPS 2022accept
We consider privacy in the context of streaming algorithms for cardinality estimation. We show that a large class of algorithms all satisfy $\epsilon$-differential privacy, so long as (a) the algorithm is combined with a simple down-sampling procedure, and (b) the input stream cardinal…