When

Start: 09/18/2013 - 1:15pm

End : 09/18/2013 - 2:15pm

End : 09/18/2013 - 2:15pm

Category

Applied Math Seminar

Speaker

Mark Huber (CMC)

Abstract

High dimensional integrals and sums arise often in applications coming from statistics, theoretical physics, and computer science. Consider the problem of approximating these integrals to within a factor of for some specified when the integrand (or summand) is nonnegative.. Monte Carlo methods for approximating these integrals work by drawing samples randomly from a family of distributions formed from the nonnegative integrand. Typically the value of these integrals is exponentially large in the problem input size, so let denote the natural logarithm of the integral in question. Previous Monte Carlo methods for such approximation used samples (suppressing the dependence on ), but the big-O notation hid factors on the order of .. In this work, a new method is presented that uses only samples, with a factor of about 16.7. As a bonus, this method is much simpler to implement then previous approaches. This is the first practical method for creating provably good approximations for these problems.

Where

CMC Campus, Adams Hall, Davidson (the largest lecture room on the first floor)