Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_K$-norm mechanism of Hardt and Talwar [HT10]. For the ${\mathrm{\ell }}_{\mathrm{\infty }}$-error, our algorithm can answer $d$ linear queries with $O(d\mathrm{/}\epsilon )$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\epsilon \le 1\mathrm{/}d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.