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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math