Efficient Statistics, in High Dimensions, from Truncated Samples
  We provide an efficient algorithm for the classical problem, going back to
Galton, Pearson, and Fisher, of estimating, with arbitrary accuracy the
parameters of a multivariate normal distribution from truncated samples.
Truncated samples from a $d$-variate normal ${\cal
N}(\mathbf{\mu},\mathbf{\Sigma})$ means a samples is only revealed if it falls
in some subset $S \subseteq \mathbb{R}^d$; otherwise the samples are hidden and
their count in proportion to the revealed samples is also hidden. We show that
the mean $\mathbf{\mu}$ and covariance matrix $\mathbf{\Sigma}$ can be
estimated with arbitrary accuracy in polynomial-time, as long as we have oracle
access to $S$, and $S$ has non-trivial measure under the unknown $d$-variate
normal distribution. Additionally we show that without oracle access to $S$,
any non-trivial estimation is impossible.
