26d ago

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

arXiv:2609.02880v1 Announce Type: new Abstract: 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,

1 reporttech

Claim audit

No BS check run yet — press ⚖ to extract this story's claims and verify them against independent sources.

All coverage

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

rss:arxiv-cscrtech26d ago kagi ↗

arXiv:2609.02880v1 Announce Type: new Abstract: 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,