Private counting of distinct elements in the turnstile model and extensions LIPIcs Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Sricharan, A. R. Steiner, Teresa Anna ddc:000 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]. Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/18156 https://research-explorer.ista.ac.at/download/18156/18166 Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>. Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a> eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.APPROX/RANDOM.2024.40 info:eu-repo/semantics/altIdentifier/issn/1868-8969 info:eu-repo/semantics/altIdentifier/isbn/9783959773485 info:eu-repo/semantics/altIdentifier/wos/001545634500040 info:eu-repo/semantics/altIdentifier/arxiv/2408.11637 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess