Locally Private Histograms in All Privacy Regimes

Clément L. Canonne, Abigail Gentle

Frequency estimation, a.k.a. histograms, is a workhorse of data analysis, and as such has been thoroughly studied under differentially privacy. In particular, computing histograms…