The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting
A lower bound of $\Omega(\log^{3/2} n)$ under approximate DP with sufficiently small fixed fixed $\delta>0$ and a lower bound of $\Omega(\log^2 n)$ under pure DP are proved, establishing the optimality of the binary tree mechanism in both settings.
Konstantina Bairaktari, Markus Engelund Dahl, Kasper Green Larsen
· 5 citations
· ⚡2