Skip to content

Back to the catalog

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

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

This arXiv preprint presents a randomness-efficient variant of the Hardt-Talwar K-norm mechanism for answering d linear queries under differential privacy, achieving O(d/ε) error in ℓ∞-norm using only O(log d) random bits. It improves on prior randomness bounds from Canonne et al. and Ghentiyala, and includes a computationally efficient version with a logarithmic increase in error, advancing the theory of differentially private query answering.

TL;DR A new randomness-efficient differentially private mechanism answers d linear queries with optimal error using only O(log d) random bits.
Open original ↗
Document

What it claims

The abstract adds one thing the summary omits: an optimality result. The O(log d) random-bit bound for answering d linear queries with O(d/ε) ℓ∞-error is optimal when ε ≤ 1/d. So in the high-privacy regime (small ε), you cannot do better on randomness — the mechanism is not just an improvement over Canonne et al. [CSV25] and Ghentiyala [Ghe26] but tight.

Two other clarifications the summary blurs: the random-bit count is an expected count, and the efficient variant's cost is an O(log d) multiplicative increase in error (the summary's "logarithmic increase" leaves the multiplicative-vs-additive question open).

Limits

This is an abstract-only arXiv page (submitted 2 Sep 2026, v1, cs.CR). No experiments, proof sketches, algorithm pseudocode, or code links are shown — the "Code, Data and Media" section lists only generic arXiv tooling, not an associated implementation. The optimality is stated only for ε ≤ 1/d; the page says nothing about tightness for larger ε. Anyone wanting to implement this must go to the PDF for the actual construction of the randomness-efficient K-norm analog.

For an engineer: this is theory advancing the randomness-utility frontier for DP linear queries, not a library to adopt. Read it if you care about the random-bit budget of DP mechanisms in the high-privacy regime; the optimality result is the reason to open the PDF rather than stop at the summary.

Organisations named here

  • Ghentiyala
  • Hardt and Talwar

Techniques named here

  • $\|\cdot\|_K$-norm mechanism

Also named here

  • Canonne et al.

Related in research