Tata Institute of Fundamental Research

A randomized algorithm for estimate volumes of convex

STCS Student Seminar
Speaker: Sourav Roy (TIFR)
Organiser: Soumyajit Pyne
Date: Friday, 26 Jul 2024, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

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.