24. Sep 2026
TCS Seminar – Differentially Private Continual Counting via Matrix Factorization: Constructions and Lower Bounds
Datum: 24. September 2026 |
14:00 –
15:00
Sprecher:
Pavel Arkhipov, ISTA
Veranstaltungsort: Mondi Seminar Room 3, Central Building
Sprache:
Englisch
Continual counting under pure differential privacy is one of the simplest and most well-studied problems in the continual observation model. Given a binary stream $x_1, \ldots, x_n \in \{0,1\}$, the goal is to release, at each time $t$, an approximation to the prefix sum $\sum_{i=1}^t x_i$. The entire output sequence must satisfy $\epsilon$-differential privacy, while making the accuracy as good as possible. We consider the maximum expected squared error over all times $t$ as our accuracy score. Very recently, it was shown that the correct asymptotics for this error is $\Theta(\epsilon^{-2} \log^3 n)$ for factorization-based mechanisms.
We give a construction using a general matrix factorization mechanism, improving the leading constant for the mean squared error. The mechanism starts from a good-quality low-dimensional factorization and lifts this factorization to arbitrarily large dimensions.
On the lower-bound side, we show a very simple $\Omega(\epsilon^{-2}\log^3 n)$ lower bound for the special case of factorizations whose matrices have entries in {0, 1}.
This talk covers a subset of our paper with Nikita Kalinin (https://arxiv.org/abs/2607.08963)
We give a construction using a general matrix factorization mechanism, improving the leading constant for the mean squared error. The mechanism starts from a good-quality low-dimensional factorization and lifts this factorization to arbitrarily large dimensions.
On the lower-bound side, we show a very simple $\Omega(\epsilon^{-2}\log^3 n)$ lower bound for the special case of factorizations whose matrices have entries in {0, 1}.
This talk covers a subset of our paper with Nikita Kalinin (https://arxiv.org/abs/2607.08963)
