Noon lecture

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

On 25.08.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 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010