Bounded Space Differentially Private Quantiles

Daniel Alabi, Omri Ben-Eliezer, Anamay Chaturvedi

Estimating the quantiles of a large dataset is a fundamental problem in both the streaming algorithms literature and the differential privacy literature. However, all existing priv…