conference paper published yes Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 A. R. Sricharan author Teresa Anna Steiner author MoHe department APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems The design and evaluation of modern fully dynamic data structures project Efficient algorithms project Static and Dynamic Hierarchical Graph Decompositions project Fast Algorithms for a Reactive Network Layer project 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]. https://research-explorer.ista.ac.at/download/18156/18166/2024_LIPICs_HenzingerM.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2024London, United Kingdom eng 1868-8969 9783959773485 2408.11637 00154563450004010.4230/LIPIcs.APPROX/RANDOM.2024.40 317 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> M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, London, United Kingdom, 2024, vol. 317. Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2024). 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). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a> Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40. Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “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. <a href="https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>. Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, vol. 317, 40, 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>. M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. 181562024-09-29T22:01:38Z2025-12-02T13:47:16Z