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