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 μ each coordinate of the sample is preserved with probability μ and otherwise is replaced by a '?'. The running time and number of samples needed for our algorithm is polynomial in n and 1/ε for each fixed μ > 0. This improves on the algorithm of Wigderson and Yehudayoff [26] that runs in quasi-polynomial time for any fixed μ > 0 and the polynomial time algorithm of Dvir et al [9] which was shown to work for μ > 0.30 by Batman et al [3]. In fact, our algorithm also works in the more general framework of Batman et al. [3] 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 [9], [3]; 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 [9].