Title: Population recovery with high erasure probability
Speaker: Mike Saks, Rutgers University
Date: Tuesday, February 12, 2013 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
In the population recovery problem (introduced by Dvir, Rao, Wigderson and Yehudayoff) one has an unknown probability distribution D on binary strings of length n and want to determine an estimate D* of the distribution such that for each string x, |D*(x)-D(x)| is at most some desired bound b. Samples can be obtained from the distribution, but each sample is obscured as follows: for each sampled string, each bit of the string is independently erased (changed to "?") with some probability q. In this talk, I'll discuss my recent work with Ankur Moitra showing that for any constant erasure probability q<1, the distribution D can be well approximated using a number of samples (and also computaton) that is polynomial in n and 1/b. This improves on the previous quasi-polynomial time algorithm of Wigderson and Yehudayoff and the polynomial time algorithm of Dvir et al which was shown to work for q<.7 by Batman et al. The algorithm we analyze is implicit in previous work; our main contribution is to analyze the algorithm. Mathematically, this amounts to showing that a certain matrix associated with the problem has a ``robust local inverse'' even though its condition number is exponentially small. We use linear programming duality to reduce the problem to a question about the behavior of polynomials on the unit complex disk, which we solve using the Hadamard 3-circle theorem from complex analysis. The talk will be self-contained; in particular, prior knowledge of robust local inverses, condition numbers, and the Hadamard 3-circle theorem will not be assumed.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math