Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
Jayadev Acharya · Ziteng Sun

Tue Jun 11th 05:05 -- 05:10 PM @ Room 102

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.

Author Information

Jayadev Acharya (Cornell University)
Ziteng Sun (Cornell/Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors