Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication

Jayadev Acharya, Ziteng Sun, Huanyu Zhang

We study the problem of estimating $k$-ary distributions under $\epsilon$-local differential privacy. $n$ samples are distributed across users who send privatized versions of th…