{"id":"arxiv/2607.28703","url":"https://arxiv.org/abs/2607.28703","tags":["cs.CR","cs.DS","math.FA"],"score":0,"title":"Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting","domain":"cs.CR","source":"arxiv","authors":["Awnon Bhowmik","Mahmudul Hasan"],"reviews":0,"subject":"cs.CR","summary":"Let $T_n$ be the lower-triangular prefix-sum matrix and let $c_{\\mathrm{F}}(T_n)$ and $c_2(T_n)$ be the factorization costs that govern the mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure $\\varepsilon$-differential privacy, for $\\varepsilon>0$. We prove $c_{\\mathrm{F}}(T_n),c_2(T_n)=Θ((\\log(n+1))^{3/2})$ with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-$\\varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-30","reactions":{}}