Locally Private Histograms in All Privacy Regimes

Explore a 26-minute lecture on locally private histograms across various privacy regimes. Delve into frequency estimation, also known as histograms or heavy hitters, a fundamental tool in data analysis that has been extensively studied under differential privacy. Examine the local model of privacy (LDP) and recent advancements in histogram computation, including algorithms that achieve order-optimal infinity error while balancing time and communication efficiency. Investigate the less understood "low-privacy" regime, its surprising intricacies, and potential empirical performance of existing algorithms beyond worst-case guarantees. Learn about joint work with Abigail Gentle, presented by Clément Canonne from the University of Sydney as part of the Extroverted Sublinear Algorithms series at the Simons Institute.