Search papers, labs, and topics across Lattice.
This paper addresses the challenge of answering linear queries with differential privacy while minimizing randomness, presenting a randomness-efficient mechanism that achieves optimal error bounds. The authors introduce an algorithm that can answer \( d \) linear queries with \( O(d / \varepsilon) \) error using only \( O(\log d) \) random bits, significantly improving upon previous works. Additionally, they offer a computationally efficient variant of the algorithm, which incurs a logarithmic increase in error, thus balancing efficiency and utility in differentially private settings.
Achieving optimal accuracy in answering linear queries with minimal randomness could redefine standards for differential privacy in practical applications.
We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.
Google Research