David Gamarnik

Computing volume of a polytope and integrals in high dimensions deterministically

Abstract We design a Correlation-Decay based quasi-polynomial time deterministic approximation algorithm for computing high dimensional integrals, applied in two settings. The first is computing the volume of an independent set polytope with restrictions. Randomized polynomial ti...