@inproceedings{18156,
  abstract     = {Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ε,δ)-differential privacy and item-level ε-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023].},
  author       = {Henzinger, Monika H and Sricharan, A. R. and Steiner, Teresa Anna},
  booktitle    = {International Conference on Approximation Algorithms for Combinatorial Optimization Problems },
  isbn         = {9783959773485},
  issn         = {1868-8969},
  location     = {London, United Kingdom},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Private counting of distinct elements in the turnstile model and extensions}},
  doi          = {10.4230/LIPIcs.APPROX/RANDOM.2024.40},
  volume       = {317},
  year         = {2024},
}