Academic

We propose novel algorithms for distribution estimation under Local Differential Privacy (LDP), focusing on both quantile and Cumulative Distribution Function (CDF) estimation. For quantile estimation, we develop an algorithm based on binary inquiries, utilizing self-normalization to achieve asymptotically normal estimators with valid inference, leading to tight confidence intervals without requiring the estimation of nuisance parameters. The method is highly efficient, fully online, and operates with $\mathcal{O}(1)$ space. An optimality result is also proven for the median estimation problem using an elegant application of a central limit theorem from Gaussian Differential Privacy (GDP). For CDF estimation, we uncover a novel connection between LDP and the current status problem in survival analysis, enabling constrained isotonic estimation via binary queries. Our method achieves uniform and $L_2$ error bounds for the entire CDF, with improvements in accuracy as grid density increases. The estimator is computationally efficient, deterministic, and free of hyperparameters, making it practical for large-scale applications. Both algorithms are validated through rigorous theoretical analysis and extensive numerical experiments, demonstrating their efficacy in distribution estimation tasks under LDP.