2026-07-24T12:23:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22655 2026-04-17T05:31:54Z ddc:004 open_access

The Randomness Complexity of Differential Privacy Canonne, Clément L. Su, Francis E. Vadhan, Salil P. differential privacy randomness geometry We initiate the study of the randomness complexity of differential privacy, i.e., how many random bits an algorithm needs in order to generate accurate differentially private releases. As a test case, we focus on the task of releasing the results of d counting queries, or equivalently all one-way marginals on a d-dimensional dataset with boolean attributes. While standard differentially private mechanisms for this task have randomness complexity that grows linearly with d, we show that, surprisingly, only log₂ d+O(1) random bits (in expectation) suffice to achieve an error that depends polynomially on d (and is independent of the size n of the dataset), and furthermore this is possible with pure, unbounded differential privacy and privacy-loss parameter ε = 1/poly(d). Conversely, we show that at least log₂ d-O(1) random bits are also necessary for nontrivial accuracy, even with approximate, bounded DP, provided the privacy-loss parameters satisfy ε,δ ≤ 1/poly(d). We obtain our results by establishing a close connection between the randomness complexity of differentially private mechanisms and the geometric notion of "deterministic rounding schemes" recently introduced and studied by Vander Woude et al. (2022, 2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Francis E. Su and Salil P. Vadhan 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.27 urn:nbn:de:0030-drops-226556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode