Pure Differentially Private Query Release via Laplace Input Smoothing

We study the offline release of a public family of k statistical queries on a database of N records from a public universe of size d, under pure ε-differential privacy. We give an efficient algorithm that, with probability at least $1-β$, answers all queries simultaneously to error O(min\1,√log(d/β)log k/Nε\). The output is a synthetic histogram on the data universe, and its running time depends polynomially on $N,d$ and k. This resolves a conjecture of Nikolov and Ullman (2021) with an efficient, polynomial-time construction. Fitzsimons (2026) recently established the same square-root error scale via an information-theoretic construction that relies on a computationally intractable Lipschitz envelope over the exponential space of possible outputs. In contrast, we introduce an input-side smoothing approach: we run a selection-only multiplicative-weights process after a single sparse Laplace perturbation of the input histogram. Departing from standard first-order stability analyses, we investigate the stability of stability by establishing a uniform lower bound on the second-order log-derivatives of the output transcript across T rounds of multiplicative weight updates. We then develop an analytic smoothing principle showing that this curvature bound allows a sparse, coordinate-wise perturbation to guarantee pure differential privacy globally, attaining optimal utility through a conceptually simple, polynomial-time pure-DP mechanism.