|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department |
Algorithms, Combinatorics and Optimization Seminar
For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University. Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...) Michael Saks Rutgers University Title: Population recovery with high erasure probability Abstract: In the population recovery problem (introduced by Dvir, Rao, Wigderson and Yehudayoff) there is an unknown probability distribution D over length n binary strings and we 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, Impagliazzo, Murray and Paturi. The algorithm we analyze is implicit in previous work on the problem; our main contribution is to analyze the algorithm. Using linear programming duality the problem is reduced to a question about the behavior of polynomials on the unit complex disk, which is answered using the Hadamard 3-circle theorem from complex analysis. There will be refreshments 30 minutes before the talk. |
