Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
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 There will be refreshments 30 minutes before the talk. |