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

Chiara Damiolini, Ian Coley and Franco Rota -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

Brooke Ogrodnik, Website

Robert Dougherty-Bliss and Doron Zeilberger --> homepage

Paul Feehan, Daniel Ketover, 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

Quentin Dubroff 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's Webpage

Organizer: Luochen Zhao

Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song Organizer's Page

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 Organizer's Webpage

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

Stephen D. Miller

Brooke Ogrodnik, Website

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

Fioralba Cakoni Seminar webpage

Ebru Toprak, Organizer

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