Rutgers Discrete Mathematics Seminar

Title: Noisy Population Recovery in Polynomial Time

Speaker: Sijian Tang, Rutgers University

Date: Monday, March 7, 2016 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


In the noisy population recovery problem of Dvir et al. [DRWY12], the goal is to learn an unknown distribution f on binary strings of length n from noisy samples. For some parameter mu, a noisy sample is generated by flipping each coordinate of a sample from f independently with probability (1-mu)/2. We assume an upper bound k on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error epsilon.

In this talk I will show that for any fixed mu > 0, one can solve this problem with complexity ploynomial in k, n and 1/epsilon. Which improves the previous best result of poly(k^(log log k), n, 1/epsilon).

Based on joint work with Anindya De and Michael Saks.