Tight Lower Bounds for Differentially Private Continual Counting

arXiv:2609.17650 · cs.DS, cs.CR · Submitted 2026-09-15 · Read on arXiv

cs.DS, cs.CR

Submitted: 2026-09-15

Updated: 2026-09-17

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Differential Privacy — 15× in this paper · explained in 4 episodes
• Differentially Private — 10× in this paper · explained in 3 episodes
• Accuracy — 6× in this paper · explained in 1 episode
• Binary Tree Mechanism — 5× in this paper
• Adam — 1× in this paper · explained in 2 episodes
• Annual ACMSIAM Symposium on Discrete Algorithms — 1× in this paper
• Differential Privacy (DP) — 1× in this paper · explained in 7 episodes
• Hamming Distance — 1× in this paper · explained in 2 episodes

Sources

• Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
• A Matrix Factorization Approach in Turnstile Streaming
• The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting
• Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
• A Near-Optimal Lower Bound for Prefix-Matrix Factorizations

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions