  Recent work in differential privacy has highlighted the shuffled model as a
promising avenue to compute accurate statistics while keeping raw data in
users' hands. We present a protocol in this model that estimates histograms
with error independent of the domain size. This implies an arbitrarily large
gap in sample complexity between the shuffled and local models. On the other
hand, the models are equivalent when we impose the constraints of pure
differential privacy and single-message randomizers.
