# Differentially Private Range Queries with Correlated Input Perturbation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 10 Feb 2024.

## Builds on (most cited first, 15 of 15)

- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Differential Privacy of Hierarchical Census Data: An Optimization Approach](https://mlsanity.com/paper/2006.15673/) (2020)
- [Optimizing Fitness-For-Use of Differentially Private Linear Queries](https://mlsanity.com/paper/2012.00135/) (2020)
- [Subspace Differential Privacy](https://mlsanity.com/paper/2108.11527/) (2021)
- [Transparent Privacy is Principled Privacy](https://mlsanity.com/paper/2006.08522/) (2020)
- [An Uncertainty Principle is a Price of Privacy-Preserving Microdata](https://mlsanity.com/paper/2110.13239/) (2021)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Integer Subspace Differential Privacy](https://mlsanity.com/paper/2212.00936/) (2022)
- [Noisy Measurements Are Important, the Design of Census Products Is Much More Important](https://mlsanity.com/paper/2312.14191/) (2023)

## Abstract (arXiv)

This work proposes a class of differentially private mechanisms for linear queries, in particular range queries, that leverages correlated input perturbation to simultaneously achieve unbiasedness, consistency, statistical transparency, and control over utility requirements in terms of accuracy targets expressed either in certain query margins or as implied by the hierarchical database structure. The proposed Cascade Sampling algorithm instantiates the mechanism exactly and efficiently. Our theoretical and empirical analysis demonstrates that we achieve near-optimal utility, effectively compete with other methods, and retain all the favorable statistical properties discussed earlier.