# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 25.8.2016 at 12:20 in S6, there is the following noon lecture:

# The Population Recovery problem

## Michael Saks

## Abstract

In the noisy population recovery problem of Dvir, Rao, Wigderson and Yehudayoff, we have an unknown distribution D on binary strings of length n and our goal is to estimate the probability of any given string under D to within some additive error epsilon. If we have access to independent samples from the distribution D, this is a simple problem of estimating the parameter of a binomial distribution and can be solved in poly(n/epsilon) time. In the "noisy" version of the problem, we can only observe noisy samples; such a sample is obtained by sampling according to D, and then flipping each coordinate independently with probability (1-mu)/2 (for some known parameter mu in (0,1).

This problem was introduced by Dvir, Rao, Wigderson and Yehudayoff (DRWY), who further assumed that we have a known upper bound k on the size of the support of D. They asked whether there is an estimation algorithm whose running time is polynomial

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page