Seminars & Colloquia Calendar

Abstract:  The population recovery problem is an idealized problem of learning in the presence of noise that was proposed in a 2012 paper of Zeev Dvir, Anup Rao, Avi Wigderson and Amir Yehudayoff (DRWY).   In this problem we have an unknown distribution D on binary strings of length n and our goal is to estimate the probability D(s)  of a particular string s within a small additive error.  We observe samples taken from the distribution, but the catch is that each sample is randomly corrupted.  What this means is that for each sample, there is a process that randomly selects each coordinate independently with probability 1-p, for some p in (0,1).  In the lossy version of the problem each selected bit is replaced by "?" and in the noisy version, each selected coordinate is replaced by a random bit. DRWY asked whether, assuming a known upper bound k on the size of the support of D, whether for each fixed p>0, there is an algorithm that estimates D(s) (in either the lossy or noisy version) in time polynomial in n, k and 1/b (where b is the allowed additive error).  The answer turns out to be yes, which was shown by Ankur Moitra and myself for the lossy version, and by Anindya De, Sijian Tang and myself for the (harder) noisy version. The solution of the noisy version builds on the lossy version, and previous work of DRWY, of Wigderson and Yehudayoff, and of Lovett and Zhang, and involves a number of  techniques: linear programming duality, complex analysis, and discrete fourier analysis. 

I'll survey this work and give some hints of the proof.