Papers With

← All papers
First page of Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

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

Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi

cs.CR Sep 2, 2026 · v1 cs.CC
formalization ai-agents geometry
Read PDF arXiv abstract
TL;DR
The authors formalized the AI-generated multi-scale secluded partition construction for the ℓ∞-norm in Lean 4 using an AI coding agent to confirm its correctness.
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, 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.
Problem

Answering d linear queries with pure differential privacy usually needs Ω(d) random bits, as with the Laplace mechanism. Prior low-randomness mechanisms reduced the bit count but at the cost of worse error.

Approach

The authors define multi-scale secluded partitions (MSSPs), which are partitions that are secluded at every scale at once. Sampling a partition cell with the exponential mechanism then gives a randomness-efficient analog of the K-norm mechanism. MSSPs are shown to exist for any K-norm via a Rogers-style random Voronoi construction. An explicit ℓ∞ construction adapts Hoza–Klivans and was checked in Lean 4 with an AI agent. An efficient ℓ∞ mechanism uses ring (annulus) sampling with partition enumeration.

Results

An ε-DP mechanism answers d linear queries with O(d/ε) error using O(log d) random bits, which is optimal when ε ≤ 1/d. A computationally efficient ℓ∞ version attains O(d log d/ε) error with the same randomness.