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 time approximation algorithms for computing the volume of a convex body have been known now for several decades, but the corresponding deterministic counterparts are not available, and our algorithm is the first of this kind. The class of polytopes for which our algorithm applies arises as linear programming relaxation of the independent set problem with the additional restriction that each variable takes value in the interval left bracket 0 comma 1 minus alpha right bracket [ 0 , 1 − α ] $[0,1-\alpha ]$ for some alpha less than 1 divided by 2 α < 1 / 2 $\alpha \lt 1/2$ . (We note that the alpha greater than or equals 1 divided by 2 α ≥ 1 / 2 $\alpha \ge 1/2$ case is trivial). The method works provided alpha greater than 1 divided by 2 minus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis α > 1 / 2 − O ( 1 / Δ 2 ) $\alpha \gt 1/2-O(1/\Delta ^2)$ , where normal upper Delta Δ $\Delta$ is the maximum degree of the graph. When normal upper Delta equals 3 Δ = 3 $\Delta =3$ (the sparsest non-trivial case), our method works provided 0.488 less than alpha less than 0.5 0.488 < α