Efficient derandomization of differentially private counting queries

Differential privacy for the 2020 census required an estimated 90 terabytes of randomness [GL20], an amount which may be prohibitively expensive or entirely infeasible to generate. Motivated by these practical concerns, [CSV25] initiated the study of the randomness complexity of differential privacy, and in particular, the randomness complexity of \(d\) counting queries. This is the task of outputting the number of entries in a dataset that satisfy predicates \(\mathcal{P}_1, \ldots, \mathcal{P}_d\) respectively. They showed the rather surprising fact that though any reasonably accurate, \(\varepsilon\)-differentially private mechanism for one counting query requires \(1 - O(\varepsilon)\) bits of randomness in expectation, there exists a fairly accurate mechanism for \(d\) counting queries which requires only \(O(\log d)\) bits of randomness in expectation.