Research map / Federated learning and privacy / Differential privacy
Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allow deletions (turnstile model) instead of insertion-only streams | DP continual CountDistinct · worst-case streams | additive error | Hurt |
| parameterize error by maximum flippancy w of the stream | item-level DP mechanism · turnstile streams | additive error | Improved |
| strengthen privacy from event-level to item-level | DP CountDistinct lower bound · turnstile streams | additive error lower bound: T^{1/4} -> T^{1/3} | Mixed |
Closest papers by meaning
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.93)
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.88)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.87)
- Continual Counting with Gradual Privacy Expiration (NeurIPS 2024 · similarity 0.87)
- Differentially Private Quantiles with Smaller Error (NeurIPS 2025 · similarity 0.87)
- Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
