School of Technology and Computer Science Seminars

A Random Polynomial Time Algorithm for Approximating The Volume of Convex Bodies

by Varun Narayanan (School of Technology and Computer Science, TIFR)

Friday, May 27, 2016 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
A randomized algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space was proposed by Martin Dyer, Alan Frieze and Ravi Kannan in 1988. The algorithm is based on a scheme for sampling nearly uniformly from within K. We motivate design of the algorithm and prove its correctness of it. The ideas used are mostly geometric and some basic theory of Markov Chain Monte Carlo methods.