# Lightweight Protocols for Distributed Private Quantile Estimation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2025.

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

- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)

## Abstract (arXiv)

Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two adaptive algorithms for estimating one quantile (e.g.~the median) when each user holds a single data point lying in a domain [B] that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). In the adaptive setting we present an varepsilon-LDP algorithm which can estimate any quantile within error α only requiring O(fraclog Bvarepsilon2α2) users, and an (varepsilon,δ)-shuffle DP algorithm requiring only widetildeO((frac1varepsilon2+frac1α2)log B) users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in B. We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-varepsilon regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.