  We give the first polynomial-time algorithm to estimate the mean of a
$d$-variate probability distribution with bounded covariance from
$\tilde{O}(d)$ independent samples subject to pure differential privacy. Prior
algorithms for this problem either incur exponential running time, require
$\Omega(d^{1.5})$ samples, or satisfy only the weaker concentrated or
approximate differential privacy conditions. In particular, all prior
polynomial-time algorithms require $d^{1+\Omega(1)}$ samples to guarantee small
privacy loss with "cryptographically" high probability, $1-2^{-d^{\Omega(1)}}$,
while our algorithm retains $\tilde{O}(d)$ sample complexity even in this
stringent setting.
  Our main technique is a new approach to use the powerful Sum of Squares
method (SoS) to design differentially private algorithms. SoS proofs to
algorithms is a key theme in numerous recent works in high-dimensional
algorithmic statistics -- estimators which apparently require exponential
running time but whose analysis can be captured by low-degree Sum of Squares
proofs can be automatically turned into polynomial-time algorithms with the
same provable guarantees. We demonstrate a similar proofs to private algorithms
phenomenon: instances of the workhorse exponential mechanism which apparently
require exponential time but which can be analyzed with low-degree SoS proofs
can be automatically turned into polynomial-time differentially private
algorithms. We prove a meta-theorem capturing this phenomenon, which we expect
to be of broad use in private algorithm design.
  Our techniques also draw new connections between differentially private and
robust statistics in high dimensions. In particular, viewed through our
proofs-to-private-algorithms lens, several well-studied SoS proofs from recent
works in algorithmic robust statistics directly yield key components of our
differentially private mean estimation algorithm.
