Computing volume of a polytope and integrals in high dimensions deterministically

Abstract

<jats:p> 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 <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline1.png"> <jats:alt-text content-type="machine-generated">left bracket 0 comma 1 minus alpha right bracket</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mo stretchy="false">[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>α</mml:mi> <mml:mo stretchy="false">]</mml:mo> </mml:math> <jats:tex-math>$[0,1-\alpha ]$</jats:tex-math> </jats:alternatives> </jats:inline-formula> for some <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline2.png"> <jats:alt-text content-type="machine-generated">alpha less than 1 divided by 2</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>α</mml:mi> <mml:mo><</mml:mo> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:math> <jats:tex-math>$\alpha \lt 1/2$</jats:tex-math> </jats:alternatives> </jats:inline-formula> . (We note that the <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline3.png"> <jats:alt-text content-type="machine-generated">alpha greater than or equals 1 divided by 2</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>α</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:math> <jats:tex-math>$\alpha \ge 1/2$</jats:tex-math> </jats:alternatives> </jats:inline-formula> case is trivial). The method works provided <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline4.png"> <jats:alt-text content-type="machine-generated">alpha greater than 1 divided by 2 minus upper O left parenthesis 1 divided by normal upper Delta squared right parenthesis</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>α</mml:mi> <mml:mo>></mml:mo> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo>−</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:msup> <mml:mi mathvariant="normal">Δ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:math> <jats:tex-math>$\alpha \gt 1/2-O(1/\Delta ^2)$</jats:tex-math> </jats:alternatives> </jats:inline-formula> , where <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline5.png"> <jats:alt-text content-type="machine-generated">normal upper Delta</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi mathvariant="normal">Δ</mml:mi> </mml:math> <jats:tex-math>$\Delta$</jats:tex-math> </jats:alternatives> </jats:inline-formula> is the maximum degree of the graph. When <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline6.png"> <jats:alt-text content-type="machine-generated">normal upper Delta equals 3</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi mathvariant="normal">Δ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:math> <jats:tex-math>$\Delta =3$</jats:tex-math> </jats:alternatives> </jats:inline-formula> (the sparsest non-trivial case), our method works provided <jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" content-type="simple" xlink:href="S0963548326100558_inline7.png"> <jats:alt-text content-type="machine-generated">0.488 less than alpha less than 0.5</jats:alt-text> </jats:inline-graphic> <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mn>0.488</mml:mn> <mml:mo><</mml:mo> <mml:mi>α</mml:mi> <mml:mo><</mml:mo>