@inproceedings{d3994a9aa277485197f20a4afa436a29,

title = "A polynomial time algorithm for lossy population recovery",

abstract = "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].",

keywords = "Complex analysis, Inverse problems, Learning",

author = "Ankur Moitra and Michael Saks",

year = "2013",

doi = "10.1109/FOCS.2013.20",

language = "English (US)",

isbn = "9780769551357",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

pages = "110--116",

booktitle = "Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013",

note = "2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 ; Conference date: 27-10-2013 Through 29-10-2013",

}