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.
Back to the ACO home page