  Local Differential Privacy protocols are stochastic protocols used in data
aggregation when individual users do not trust the data aggregator with their
private data. In such protocols there is a fundamental tradeoff between user
privacy and aggregator utility. In the setting of frequency estimation,
established bounds on this tradeoff are either nonquantitative, or far from
what is known to be attainable. In this paper, we use information-theoretical
methods to significantly improve established bounds. We also show that the new
bounds are attainable for binary inputs. Furthermore, our methods lead to
improved frequency estimators, which we experimentally show to outperform
state-of-the-art methods.
