Computing volume of a polytope and integrals in high dimensions deterministically

Source abstract

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 < α < 0.5 $0.488\lt \alpha \lt 0.5$ . Our second setting is to compute the integral of a multi-dimensional separable function, supported by some underlying hyper-graph structure, appropriately defined. Equivalently, our integral is the partition function of a graphical model with continuous potentials. For our method to work, we require that the domain is bounded and the hyper-edge potentials are positive and bounded on the domain. We further assume that the potentials have upper and lower bounds separated by a multiplicative factor of 1 plus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis 1 + O ( 1 / Δ 2 ) $1 + O(1/\Delta ^2)$ , where normal upper Delta Δ $\Delta$ is the maximum degree of the graph.