Seminars & Colloquia Calendar

Download as iCal file

Mathematical Physics Seminar

Population Recovery in polynomial time

Mike Saks - Rutgers University 

Location:  Hill 705
Date & time: Thursday, 04 October 2018 at 2:00PM - 3:00PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.