# Seminars & Colloquia Calendar

## 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.

R. Shapiro Organizer's Page

Charles Weibel Organizer's Page

Brooke Logan

Wujun Zhang Organizer's webpage

P. Gupta, X.Huang and J. Song Organizer's webpage

Swastik Kopparty, Sepehr Assadi Seminar webpage

Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage

Yonah Biers-Ariel, Mingjia Yang, and Doron Zeilberger --> homepage

Paul Feehan, Manousos Maridakis, Natasa Sesum Organizer's webpage

Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage

Jason Saied Seminar webpage

Brian Pinsky, Rashmika Goswami website

Corrine Yap Organizer's webpage

James Holland; Organizer website

Edna Jones Organizer's webpage

Brooke Ogrodnik website

Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum

Organizer: Luochen Zhao

Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song

Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage

Simon Thomas website

Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page

Joel Lebowitz, Michael Kiessling

Yanyan Li, Haim Brezis

Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Alex Walker seminar website

Stephen D. Miller

Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum

Yael Davidov Seminar webpage

Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page

Ebru Toprak, Organizer

Fioralba Cakoni Seminar webpage

Organizer: Vladimir Retakh Organizer's webpage

- Show events from all categories

## 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.*