# A bounded-noise mechanism for differential privacy

arXiv: https://arxiv.org/abs/2012.03817 · HTML: https://mlsanity.com/paper/2012.03817/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2020.

## Built on by (most cited first, 15 of 15)

- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [A Central Limit Theorem for Differentially Private Query Answering](https://mlsanity.com/paper/2103.08721/) (2021)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Privacy Amplification for the Gaussian Mechanism via Bounded Support](https://mlsanity.com/paper/2403.05598/) (2024)
- [AnoFel: Supporting Anonymity for Privacy-Preserving Federated Learning](https://mlsanity.com/paper/2306.06825/) (2023)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Private Multi-Winner Voting for Machine Learning](https://mlsanity.com/paper/2211.15410/) (2022)
- [Differentially Private Federated Learning without Noise Addition: When is it Possible?](https://mlsanity.com/paper/2405.04551/) (2024)
- [Predicting adaptively chosen observables in quantum systems](https://mlsanity.com/paper/2410.15501/) (2024)
- [Efficient Adaptive Data Analysis over Dense Distributions](https://mlsanity.com/paper/2602.07732/) (2026)
- [Fixed-Parameter Tractability of Private Synthetic Data Generation](https://mlsanity.com/paper/2606.11283/) (2026)
- [Publicly-Verifiable Certificates for Statistical Algorithms](https://mlsanity.com/paper/2607.15528/) (2026)
- [How Reusable Are Benchmarks with Richer Feedback?](https://mlsanity.com/paper/2609.32109/) (2026)

## Abstract (arXiv)

We present an asymptotically optimal (ε,δ) differentially private mechanism for answering multiple, adaptively asked, Delta-sensitive queries, settling the conjecture of Steinke and Ullman [2020]. Our algorithm has a significant advantage that it adds independent bounded noise to each query, thus providing an absolute error bound. Additionally, we apply our algorithm in adaptive data analysis, obtaining an improved guarantee for answering multiple queries regarding some underlying distribution using a finite sample. Numerical computations show that the bounded-noise mechanism outperforms the Gaussian mechanism in many standard settings.