Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization
Date
Thursday, March 5, 2026 11:30 - 12:30
Speaker
Joel Daniel Andersson (ISTA)
Location
Moonstone Bldg / Ground floor / Seminar Room G (I24.EG.030g)
Series
Seminar/Talk
Contact
We study differentially-private statistics in the fully dynamic continual observation model, where many updates can arrive at each time step, and updates to a stream can involve both insertions and deletions of an item.
Earlier work (e.g., Jain et al., NeurIPS 2023 for counting distinct elements; Raskhodnikova & Steiner, PODS 2025 for triangle counting with edge updates) reduced the respective cardinality estimation problem to continual counting on the difference stream associated with the true function values on the input stream.
In such reductions, a change in the original stream can cause many changes in the difference stream.
This poses a challenge for applying private continual counting algorithms to obtain optimal error bounds.
Our work improves the accuracy of several such reductions by studying the induced neighboring relation more closely.
The improvement stems from tight analysis of known factorization mechanisms for the prefix-sum matrix in this setting.
In particular, we show how the square-root factorization (Henzinger et al., SODA 2023; Fichtenberger et al., ICML 2023) can be employed to give concrete improvements in accuracy over past work based on the binary tree mechanism.
We instantiate our framework for the problems of counting distinct elements, estimating degree histograms, and estimating triangle counts (under a slightly relaxed privacy model), showing improved accuracy for a large range of parameters.
Based on joint work with Palak Jain and Satchit Sivakumar (https://arxiv.org/abs/2601.02257).