Discrete Distribution Estimation under Local Privacy
  The collection and analysis of user data drives improvements in the app and
web ecosystems, but comes with risks to privacy. This paper examines discrete
distribution estimation under local privacy, a setting wherein service
providers can learn the distribution of a categorical statistic of interest
without collecting the underlying data. We present new mechanisms, including
hashed K-ary Randomized Response (KRR), that empirically meet or exceed the
utility of existing mechanisms at all privacy levels. New theoretical results
demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at
different privacy regimes.
