On 25.08.2016 at 12:20 in S6, there is the following noon lecture:
The Population Recovery problem
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
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010