Speaker: | Sourav Roy (TIFR) |
Organiser: | Soumyajit Pyne |
Date: | Friday, 26 Jul 2024, 16:00 to 17:00 |
Venue: | A-201 (STCS Seminar Room) |
I will present a randomized volume algorithm from the paper "Volume Estimates and Rapid Mixing " by Bela Bollobas. The goal is to find a fully polynomial approximation scheme (FPRAS) for approximating the volume of a convex body K in R^n. A randomized algorithm that runs in time polynomial in <K>, 1/ (\epsilon) and log(1/\nu), and with probability at least (1 − \nu) produces an \epsilon-approximation to vol(K). Here the input is (r, R, n) for K satisfying rB^n \subset K \subset RB^n with <K> = n + <r> + <R>, where <x> is the number of binary digits of a dyadic rational x.