The lossy population recovery problem is a basic problem in learning theory, where we are given samples from a distribution on binary strings. The catch is that each coordinate is independently replaced with a '?' with probability $1 - mu$, and so samples from one string can easily be confused with another. We give the first polynomial time learning algorithm for this problem, for any $mu > 0$. 

Interestingly, the heart of our problem is that we are faced with a linear inverse problem $Ax = b$, where the condition number of $A$ is exponentially large. But because we are only interested in certain coordinates of the solution we can bypass this problem by constructing an alternative local inverse using tools from complex analysis.

This is based on joint work with Mike Saks.