Order-Invariant Cardinality Estimators Are Differentially Private

Charlie Dickens, Justin Thaler, Daniel Ting

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)…