Metraipolis › archive › dc_f221d8138dbd

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries — arXiv:2609.02880

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.02880
License (as archived)
CC0-1.0
Archived
2026-10-17T04:41:11.696Z
SHA-256 of the archived text
7d71b91d93ac9d7221859465a92826230568fda79c0e2f66b58e3ff5d9899a6a
Stable URL of this page
https://metraipolis.com/documento/dc_f221d8138dbd

How to cite

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries — arXiv:2609.02880 — arXiv (en), https://arxiv.org/abs/2609.02880 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f221d8138dbd (Metraipolis archive dc_f221d8138dbd, sha256 7d71b91d93ac9d7221859465a92826230568fda79c0e2f66b58e3ff5d9899a6a)
BibTeX
@misc{dcf221d8138dbd,
  title = {Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries — arXiv:2609.02880},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.02880},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f221d8138dbd; sha256 7d71b91d93ac9d7221859465a92826230568fda79c0e2f66b58e3ff5d9899a6a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02880. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-03 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.02880 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:09:09.367Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).