A Polynomial Time Algorithm for Lossy Population Recovery
  We give a polynomial time algorithm for the lossy population recovery
problem. In this problem, the goal is to approximately learn an unknown
distribution on binary strings of length $n$ from lossy samples: for some
parameter $\mu$ each coordinate of the sample is preserved with probability
$\mu$ and otherwise is replaced by a `?'. The running time and number of
samples needed for our algorithm is polynomial in $n$ and $1/\varepsilon$ for
each fixed $\mu>0$. This improves on algorithm of Wigderson and Yehudayoff that
runs in quasi-polynomial time for any $\mu > 0$ and the polynomial time
algorithm of Dvir et al which was shown to work for $\mu \gtrapprox 0.30$ by
Batman et al. In fact, our algorithm also works in the more general framework
of Batman et al. in which there is no a priori bound on the size of the support
of the distribution. The algorithm we analyze is implicit in previous work; our
main contribution is to analyze the algorithm by showing (via linear
programming duality and connections to complex analysis) that a certain matrix
associated with the problem has a robust local inverse even though its
condition number is exponentially small. A corollary of our result is the first
polynomial time algorithm for learning DNFs in the restriction access model of
Dvir et al.
