Differentially Private Medians and Interior Points for Non-Pathological
  Data
Maryam Aliakbarpour Rose Silver Thomas Steinke Jonathan Ullman
We construct differentially private estimators with low sample complexity
that estimate the median of an arbitrary distribution over $\mathbb{R}$
satisfying very mild moment conditions. Our result stands in contrast to the
surprising negative result of Bun et al. (FOCS 2015) that showed there is no
differentially private estimator with any finite sample complexity that returns
any non-trivial approximation to the median of an arbitrary distribution.