Skip to yearly menu bar Skip to main content


Oral

Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters

Jayadev Acharya · Ziteng Sun

[ ] [ Visit Privacy ]
[ Slides [ Video

Abstract:

We consider the problems of distribution estimation and frequency/heavy hitter estimation under local differential privacy (LDP), and communication constraints. While each constraint has been studied separately, optimal schemes for one are sub-optimal for the other. We provide a one-bit \eps-LDP scheme that requires no shared randomness and has the optimal performance. We also show that a recently proposed scheme (Acharya et al., 2018b) for \eps-LDP distribution estimation is also optimal for frequency estimation. Finally, we show that if we consider LDP schemes for heavy hitter estimation that do not use shared randomness then their communication budget must be w(1) bits.

Chat is not available.