# Computing the Volume of a Restricted Independent Set Polytope
Deterministically

David Gamarnik & Devin Smedira Massachusetts Institute of Technology, Sloan
School of Management, Operations Research Center, Institute for Data, Systems
and Society. Support from NSF grants CISE-2233897 and DMS-2015517 is
gratefully acknowledgedMassachusetts Institute of Technology, Operations
Research Center

###### Abstract

We construct a quasi-polynomial time deterministic approximation algorithm for
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
$[0,1-\alpha]$ for some $\alpha<1/2$. (We note that the $\alpha\geq 1/2$ case
is trivial).

We use the correlation decay method for this problem applied to its
appropriate and natural discretization. The method works provided
$\alpha>1/2-O(1/\Delta^{2})$, where $\Delta$ is the maximum degree of the
graph. When $\Delta=3$ (the sparsest non-trivial case), our method works
provided $0.488<\alpha<0.5$. Interestingly, the interpolation method, which is
based on analyzing complex roots of the associated partition functions, fails
even in the trivial case when the underlying graph is a singleton.

##  1 Introduction

We consider the problem of designing deterministic polynomial time algorithm
for the problem of computing the volume of a polytope. Namely, given a
polytope $\mathcal{P}$ described by a sequence of inequalities
$\mathcal{P}=\\{x:Ax\leq b\\}$, where matrix $A$ and vector $b$ are given as
problem input, the goal is to compute the volume (Lebeasgue measure) of
$\mathcal{P}$ using deterministic algorithms with polynomial running time.

It is known that solving this problem exactly is $\\#P$-hard even in very
restricted cases [8], and thus it is unlikely that exact computation of the
volume is possible with polynomial time algorithms. The focus thus has shifted
to designing approximation algorithms. In this case the algorithms do exist,
thanks to the celebrated work by Dyer, Frieze and Kannan [7], who have
successfully constructed Markov Chain Monte Carlo (MCMC) based algorithm which
provides Fully Polynomial Time Randomized Approximation Scheme (FPRAS), when
the problem input is any convex body, and not necessarily a polytope.

FPRAS is nearly golden standard in the field of approximation algorithms, the
only caveat being its reliance on randomization. This raises a question
whether a deterministic counterparts exist for the same problem.
Unfortunately, in the case when the input is a general convex body described
with an assistance of an appropriate oracle, deterministic polynomial
algorithms provably do not exist, thanks to a clever argument by Bárány and
Füredy [4]. The special case, though, when the input is explicitly given as a
polytope as opposed to oracle based description is a totally different matter
and here the existence of deterministic approximation algorithms is not ruled
out. This question is the central focus of this work.

The existence of deterministic counterparts to otherwise randomized algorithms
is a central question in theoretical computer science. It is widely believed
that any problem which admits polynomial time randomized algorithm (namely
belongs to the either of the classes RP or BPP) must admit a deterministic
counterpart (namely an algorithm in P) [15]. While proving this conjecture in
full generality appears out of reach, for many special cases this has been
successfully achieved, the problem of counting in graphs being one of them,
which we turn to next.

Recently we have witnessed a dramatic progress in designing deterministic
approximation algorithms for the problem of counting in graphs. Here the
problem is as follows: given a graph and given a combinatorial structure of a
particular type (independent set, matching, proper coloring, etc.) the goal is
to compute approximately the number of such structures in the graph (exact
computation is #P-hard again in most cases). A generalization of this problem
involves computing the object known as the partition function, a canonical
object arising in the field of statistical physics.

For a while the only algorithms for solving this problem was MCMC-based as
thus relied on randomization. In 2005 the correlation decay method was
introduced simultaneously and independently by Bandyobapdhyay and Gamarnik [2,
3] and Weitz [16], which led to deterministic approximation algorithms for
counting in graphs. Loosely speaking the correlation decay means, that when
the solution is sampled from the associated Gibbs distribution (uniformly at
random in particular), the marginal distribution associated with nodes at
large distances are approximately product form. While the algorithm in [2, 3]
was restricted to graphs with growing girth, the algorithm in [16], did not
have such restrictions and led for the first time to a Fully Polynomial Time
Deterministic Approximation Scheme (FPTDAS) – truly the strongest algorithm
one could hope for for this problem. The algorithm was based on an extremely
ingineous idea of relating the problem of counting in graphs to the problem of
counting in the associated self-avoiding tree, appropriately defined. The
exponent of the running time was improved recently to the best possible by an
important developments [1] based on spectral independence.

Later on another very powerful method for graph counting problems was
introduced by Barvinok [5]. The method is based on viewing the partition
function as a complex variable polynomial and showing that the logarithm of
this polynomial is well approximated by its low order Taylor terms provided
the zeros of the polynomials are outside of a certain complex region
containing $0$ and $1$. Remarkably, the power of the method evidently
coincides with the correlation decay method, also leading to FPTDAS in the
same regimes. A partial explanation for this was given in [10] and [13].

Since the volume computation can be viewed as a idealized version of counting,
it is only natural to attempt either the correlation decay or the
interpolation method to address this problem. We adopt the correlation decay
method in this paper and, at the same time, show that the interpolation method
runs into some technical barriers which we explain below. We restrict our
attention to polytopes which are linear programming relaxation of the
independent set problem and introduce the set up next. We do conjecture though
that the method extends far beyond this set up, although serious technical
challenges do arise which we also discuss.

Consider a simple undirected graph $G$ on the node set $V$ and edge set $E$.
An independent set is any subset of nodes $I\subset V$ which spans no edges.
Namely, for every $u,v\in E$ it is the case that $(u,v)\notin E$. Associate
with every node $u\in V$ a variable with range $[0,1]$ and with every edge
$(u,v)$ a linear constraint $x_{u}+x_{v}\leq 1$. This gives a rise to a
polytope we denote by $\mathcal{P}_{\rm IS}(G)$. Computing the volume of this
polytope algorithmically is our focus.

If we consider a further restriction $x_{u}\in\\{0,1\\}$ for every node and
count the number of solutions, this clearly corresponds to the number of
independent sets in the graph $G$, which is the subject of [2, 3, 16] and many
follow up papers. Indeed, Weitz’ algorithm applies to this setting when the
largest degree $\Delta$ of the graph $G$ does not exceed $5$. Importantly, in
a dramatic development by Sly [14], it was shown that approximating the number
of independent sets in graphs when $\Delta$ is allowed to be at least $6$ is
NP-hard to compute.

At the same time, the approximation algorithm of [7] indicates that such
hardness result does not hold for the volume computation problem. Thus, it is
likely that the correlation decay holds for the model, appropriately defined.
A partial progress in this direction was achieved in [11]. There the
independent set linear programming relaxation problem described above was
considered when the underlying graph is a regular tree. It was established
that indeed, consistently with the hypothesis above, the independent set
polytope on regular trees exhibits correlation decay for _all_ degrees.
Unfortunately, the method utilized in this paper is not adoptable to graphs
with varying degree and new methods are needed. This is what we partially
achieve in this paper.

We now describe our main result. We consider the problem of computing the
volume of the the polytope $\mathcal{P}_{\rm IS}(G)$ with an additional
assumption that each variable $x_{v}$ is restricted to be in the interval
$[0,1-\alpha]$ for some $\alpha<1/2$. We denote this polytope by
$\mathcal{P}_{\rm IS}(G,\alpha)$. We note that the case $\alpha\geq 1/2$ is
trivial, as in this case the constraints $x_{u}+x_{v}\leq 1$ become redundant
and the volume of the polytope is $(1/2)^{|V|}$ trivially. The case
$\alpha<1/2$ however is a different story and this is where we achieve a
partial progress. We design a deterministic approximation algorithm for this
problem with the running time $|V|^{O(\log|V|/\epsilon)}$ for any fixed
$\epsilon>0$. Namely, the value produced by the algorithm normalized by the
correct volume is within the interval $(1-\epsilon,1+\epsilon)$. Thus our
algorithm is quasi-polynomial time. We achieve this for the range of
$\Delta$-dependent values of $\alpha$ where $\Delta$ is the maximum degree of
the graph $G$. Specifically, when $\Delta=3$, which corresponds to the
sparsest graphs for which the problem is non-trivial, our algorithm applies
when $\alpha>0.488$. Asymptotically, our algorithm works when
$\alpha>1/2-O(1/\Delta^{2})$. Admittedly, the regime of applicability of our
method is very narrow, in light of the fact that the problem trivializes when
$\alpha=1/2$. Our analysis shows, however, that the problem is very subtle
even in this very narrow regime.

We now discuss our algorithm and the rationale for the restriction involving
the parameter $\alpha$. Our algorithm is based on establishing the correlation
decay property on the appropriately discretized version of the problem. Namely
the problem of counting the number of solutions of the system of equations
$x_{u}+x_{v}\leq N,(u,v)\in E$ when $x_{u}$ are restricted to lie in the set
$0,1,2,\ldots,N$ for large enough integer value $N$. An approach for proving
the correlation decay property, specifically for non-binary models, is to
establish a contraction of the functions associated with computation of
marginal values, appropriately defined. The contraction in its own turn can be
established by showing that $\|\cdot\|_{1}$ norm of the gradient of this
functions is strictly smaller than $1$. This method of establishing the
correlation decay property was introduced in [9] and became a fairly canonical
approach to similar problems later on. The earlier method introduced by Weitz
[16] is based on establishing a certain monotonicity property on the
associated self-avoiding tree, (a special case of the computation tree), is
evidently limited to 2-valued models, as opposed to the $N+1$-valued setting,
which is the setting in our case.

Unfortunately, the $\|\cdot\|_{1}$-contraction _does not_ hold for the model
$\mathcal{P}_{\rm IS}(G)$, even in the special case when the underlying graph
is a regular tree, even though the correlation decay property does hold for
this model as per the main result in [11]. This was verified by us numerically
as we report in Section 7. However, introducing the additional restriction of
the form $x_{u}\in[0,1-\alpha]$ does induce the $\|\cdot\|_{1}$ contraction,
and this constitutes the main technical result of our paper. The proof of the
contraction is somewhat involved, but fairly elementary.

While we have established the correlation decay property for this, admittedly
a rather restricted case of polytopes, we do conjecture that it holds in full
generality. The existence of a polynomial time approximation algorithms for
all convex bodies on the one hand, the tight connection between the problem of
counting in graphs and correlation decay, on the other hand, strongly suggests
the validity of this conjecture. Thus we pose the following conjecture: _the
Gibbs distribution associated with the Lebesgue measure of a polytope exhibits
the correlation decay property_. Resolving this conjecture even for the
independent set polytope, or polytopes associated with other combinatorial
structures is a very interesting special case for this conjecture.

We close this section by noting that the alternative method of counting based
on the polynomial interpolation method does not appear to be effective for the
problem of volume computation even in the trivial case when the underlying
graph $G$ consists of a single node $u$ (with no loops). In this case, after
the discretization the set of feasible solutions is trivially the entire range
$0,1,2,\ldots,N$. The natural complex valued polynomial associated with this
case is then $p(z)=\sum_{0\leq k\leq N}z^{k}=(1-z^{N+1})/(1-z)$.
Unfortunately, this polynomial has the sequence of roots $z_{i}=e^{2\pi
ik/(N+1)},k=1,2,\ldots,N$ concentrating densely around $1$. This prevents the
construction of a zero-free connected region containing $1$, which is the
basis of the interpolation approach. We conjecture, however, that this problem
might be somewhat artificial and some clever modification of the interpolation
method can be adopted which avoids this pitfall. What this alternative
construction should look like, however, is not entirely clear to us, and we
leave it as another very interesting open question.

We provide a brief overview of the remaining sections. Section 2 will more
formally define the problem outlined above and present the main result.
Section 3 of this paper will present a discretization of the volume problem,
and present some preliminary results. Section 4 will present the proof of the
core correlation decay property necessary to design the approximate counting
algorithms. In Section 5, we will present an algorithm and prove the first of
our two core results below. In Section 6, we will relate the discretization we
introduce to volumes to prove the main result of this paper. Finally, Section
7 will discuss the barriers to extending our results to the polytopes
$\mathcal{P}_{\text{IS}}(G)$.

##  2 Definitions and the Main Result

We repeat here the definitions of the independent set polytope
$\mathcal{P}_{\text{IS}}(G)$, as well as the restricted independent set
polytope $\mathcal{P}_{\text{IS}}(G,\alpha)$ from the introduction for
convenience.

Consider a simple undirected graph $G=(V,E)$ with $m=|V|$ vertices. Let
$\Delta$ denote the maximum degree of the graph. Namely, letting
$d(v)=|\\{u:(u,v)\in E\\}|$ be the degree of the node $v$, $\Delta=\max_{v\in
V}d(v)$. The independent set polytope $\mathcal{P}_{\text{IS}}(G)$ is defined
as

$\mathcal{P}_{\text{IS}}(G)=\\{\textbf{x}\in\mathbb{R}^{m}|0\leq x_{v}\leq
1,\forall v\in V,x_{u}+x_{v}\leq 1,\forall(u,v)\in E\\}.$

Fix any Restriction Parameter $\alpha\in(0,1)$. The restricted independent set
polytope $\mathcal{P}_{\text{IS}}(G,\alpha)$ is defined as

$\mathcal{P}_{\text{IS}}(G,\alpha)=\\{\textbf{x}\in\mathbb{R}^{m}|0\leq
x_{v}\leq 1-\alpha,\forall v\in V,x_{u}+x_{v}\leq 1,\forall(u,v)\in E\\}.$

We denote by $\operatorname{Vol}(\mathcal{P}_{\text{IS}}(G,\alpha))$ the
volume of this polytope. Specifically,

$\displaystyle\operatorname{Vol}(\mathcal{P}_{\text{IS}}(G,\alpha))=\int
1\left(\textbf{x}\in\operatorname{Vol}(\mathcal{P}_{\text{IS}}(G,\alpha))\right)d\lambda(\textbf{x}),$

where $\lambda$ denotes the Lebesgue measure in $\mathbb{R}^{m}$. Our goal is
computing $\operatorname{Vol}(\mathcal{P}_{\text{IS}}(G,\alpha))$
algorithmically.

We define $\alpha_{\Delta}\in(0,1)$ as the smallest $\alpha$ satisfying

$\displaystyle\frac{2\Delta(1-\alpha)}{\alpha}\left(\frac{(1-\alpha)^{d}}{\alpha^{d}}-1\right)=1.$
(0)

We now formally state the main result of this work.

######  Theorem 1 (Approximating the Volume of
$\mathcal{P}_{\text{IS}}(G,\alpha)$).

There exists an algorithm which for any graph $G$, any
$\alpha>\alpha_{\Delta}$, and any $\epsilon>0$, produces a value $\tilde{V}$
satisfying

$\displaystyle
1-\epsilon\leq{\tilde{V}\over\operatorname{Vol}(\mathcal{P}_{\text{IS}}(G,\alpha))}\leq
1+\epsilon.$

The running time of the algorithm is
$\left(\frac{m}{\epsilon}\right)^{O(\log(m/\epsilon))}$ time, where $m=|V|$ is
the number of nodes in the graph. In particular, the algorithm is a Fully
Quasi-Polynomial Time Deterministic Approximation Scheme (FQPTDAS).

As mentioned in the introduction, we believe that this result can be improved
to obtain a FPTDAS, namely removing the dependence on $m$ and $\epsilon$ in
the exponent. We note that several of the original approximation results based
on the interpolation method were first of quasi-polynomial time, and later
improved to be genuinely polynomial running time algorithms [12].

Next we introduce our main technical result, the correlation decay property on
the associated computation tree, which is the basis of our algorithm and
Theorem 1. Our first step is discretizing the problem and thus converting the
problem of volume computation to the problem of counting. Fix a large positive
integer $N$, referred to as the Relaxation Parameter, and define the set

$\displaystyle\mathcal{D}_{\rm
IS}(G,\alpha,N)=\\{\textbf{x}\in\mathbb{Z}_{+}^{m}:x_{v}\leq(1-\alpha)N,\forall
v\in V,x_{u}+x_{v}\leq N,\forall(u,v)\in E\\},$ (1)

and the associated counting measure known as the partition function

$\displaystyle Z(G)=|\mathcal{D}_{\rm IS}(G,\alpha,N)|.$ (2)

For linguistic convenience, we will refer the the vectors
$\textbf{x}\in\mathcal{D}_{\rm IS}(G,\alpha,N)$ as the Relaxed Independent
Sets of the graph $G$. Roughly speaking, as we will make more precise in
Section 6, the value of $Z(G)$ is the volume of $\mathcal{P}_{\rm
IS}(G,\alpha)$ scaled by $N^{m}$. Our main focus is thus developing an
approximation algorithm for estimating $Z(G)$.

Due to the recursive nature of the algorithm, we will need to consider the set
further restricted by a set of equalities of the form $x_{v}=n$. This type of
constraint effectively eliminates one of the $n$ coordinates. A collection of
such constraints will be generically denoted by $\beta$, and any time an
additional constraint of the form $x_{v}=n$ is added, the collection is
updated as $\beta^{\prime}=\beta\cup(v\leftarrow n)$, which, with some abuse
of notation, we write as $(\beta,v\leftarrow n)$. Given a collection $\beta$
of such constraints we define $\mathcal{D}_{\rm IS}(G,\alpha,N,\beta)$ as the
set of points in the set $\mathcal{D}_{\rm IS}(G,\alpha,N)$ satisfying the
constraints in $\beta$. We will denote this set by $\mathcal{D}(G,\beta)$ and
refer the its members as the Restricted Relaxed Independent Sets of $G$. We
define by $Z(G,\beta)$ the cardinality of this set.

We now introduce the Gibbs distribution associated with the counting measure
$Z(G,\beta)$. This is just a uniform probability measure on the set
$\mathcal{D}(G,\beta)$. Namely, we assign probability $1/Z(G,\beta)$ to each
point in $\mathcal{D}(G,\beta)$. For each node $v\in V$ and each integer
$n\in[0,N]$, we denote by $x(G,v\leftarrow n,\beta)$ the probability that
$x_{v}$ takes value $n$ under this measure. Note that

$\displaystyle x(G,v\leftarrow n,\beta)={Z(G,(\beta,v\leftarrow n))\over
Z(G,\beta)}.$

It is possible for both the numerator and the denominator of this expression
to be 0. In this case, we define $x(G,v\leftarrow n,\beta)$ to be 0.

A standard approach for computing the partition function $Z(G)$ is to compute
marginals $x(G,v\leftarrow n,\beta)$ up to inverse polynomial in $m$
multiplicative errors. This approach goes as follows. Fix any ordering of
nodes $v_{1},\ldots,v_{n}$ and fix any sequence of values $n_{1},\ldots,n_{m}$
in $[0,(1-\alpha)N]$. Specifically we may take all of them equal to zero. Let
$\beta_{k}$ be the sequence of constraints $v_{j}\leftarrow 0,1\leq j\leq k$.
We have the following telescoping property

$\displaystyle Z(G)$ $\displaystyle=x^{-1}(G,v_{1}\leftarrow 0)Z(G,\beta_{1})$
$\displaystyle=x^{-1}(G,v_{1}\leftarrow 0)x^{-1}(G,v_{2}\leftarrow
0,\beta_{1})Z(G,\beta_{2})$ $\displaystyle=\prod_{1\leq k\leq
m}x^{-1}(G,v_{k}\leftarrow 0,\beta_{k-1}),$

under the convention that $\beta_{0}$ is an empty set of constraints. Suppose
we algorithmically produce a sequence of estimations $y(G,v_{k}\leftarrow
0,\beta_{k-1}),1\leq k\leq m$ of $x(G,v\leftarrow k,\beta_{k-1})$ up to
multiplicative precision say $1/m^{2}$. Namely,

$\displaystyle 1-1/m^{2}\leq{x(G,v_{k}\leftarrow 0,\beta_{k-1})\over
y(G,v_{k}\leftarrow 0,\beta_{k-1})}\leq 1+1/m^{2}.$

Then $\hat{Z}(G)\triangleq\prod_{k}y^{-1}(G,v_{k}\leftarrow 0,\beta_{k-1})$
satisfies

$\displaystyle(1-1/m^{2})^{m}=1-O(1/m)\leq{\hat{Z}(G)\over
Z(G)}\leq(1+1/m^{2})^{m}=1+O(1/m),$

and hence we obtain our goal of estimating $Z(G)$ up to multiplicative
approximation better than any fixed constant $\epsilon$ for large $m$. Thus
our focus now is designing an algorithm for producing approximations
$y(G,v\leftarrow n,\beta)$ of $x(G,v\leftarrow n,\beta)$.

Our next step towards stating the correlation decay property is establishing a
recursion structure exhibited by the marginal probabilities $x(G,v\leftarrow
m,\beta)$. This recursive structure in full generality was introduced in [9]
and we adopt it here as well.

We fix a graph $G=(V,E)$, node $v\in V$, and any set of constraints $\beta$.
Let $v_{1},\ldots,v_{d}$ be the neighbors of $v$, where $d=d(v)$ is the degree
of the node. For any sequence of integers
$n,n_{1},\ldots,n_{d}\in[0,(1-\alpha)N]$, we denote $(n_{1},\ldots,n_{i})$ by
$\bar{n}_{i}$ for short and consider the associated marginal probabilities

$\displaystyle x^{i}(\bar{n}_{i})\triangleq x\left(G\setminus
v,v_{i}\leftarrow n_{i},(\beta,\left(v_{j}\leftarrow n_{j},1\leq j\leq
i-1\right)\right)).$

Namely, this is the probability that when nodes $v_{1},\ldots,v_{i-1}$ are
assigned values $n_{1},\ldots,n_{i-1}$ respectively (thus updating the set of
constraints from $\beta$ to $\beta,v_{j}\leftarrow n_{j},j\leq i-1$), and $v$
is eliminated from $G$, the node $v_{i}$ receives value $n_{i}$. The vector
$(x^{i}(\bar{n}_{i}),1\leq i\leq d)$ of marginals is denoted by x. For every
$k$, we let $S_{k}=[0,\min\left(N-k,(1-\alpha)N\right)]$. Define the sequence
$\left(f_{n},n\in[0,(1-\alpha)N]\right)$ as follows:

$\displaystyle f_{n}(\textbf{x})=\frac{\sum\limits_{n_{1},\ldots n_{d}\in
S_{n}}x^{1}(\bar{n}_{1})\ldots
x^{d}(\bar{n}_{d})}{\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{m}}x^{1}(\bar{n}_{1})\ldots x^{d}(\bar{n}_{d})}.$ (3)

The recursive structure is stated in the following proposition which will be
proved in the next section.

######  Proposition 2.

The following relation holds for every $n\in[0,(1-\alpha)N]$:

$\displaystyle x(G,v\leftarrow n,\beta)=f_{n}(\textbf{x}).$

Ultimately, we will use the recursion (3), to compute estimations y of the
true marginal probabilities x recursively. We will introduce the notion of a
Feasible Marginal Distribution for this problem setup in Section 3.2, and show
that both the true marginals x and the recursive estimates y satisfy the
definition. Our main correlation decay result states that provided two vectors
x and y are Feasible Marginal Distributions and $\alpha$ satisfies ( ‣ 2), the
following contraction property holds for every $n\in[0,(1-\alpha)N]$ and for
some $0<c=c(\alpha)<1$,

$\displaystyle|f_{n}(\textbf{y})-f_{n}(\textbf{x})|\leq
c\|\textbf{y}-\textbf{x}\|_{\infty}.$

Namely, every iteration of the recursion encoded in $f_{n}$ decreases the
estimation error geometrically. Provided the number of iterations is of the
order $\Theta(\log n)$, we will obtain the required upper $1/n^{\Omega(1)}$ on
the estimation error. This is the correlation decay on the computation tree
property which is the main technical underpinning of our work.

##  3 Preliminary Technical Results

This section will be primarily focused on providing a complete proof of
Proposition 2. We will then provide a definition of a Feasible Marginal
Distribution and establish a few related properties.

###  3.1 Proof of Proposition 2

We will now show how to write an expression for $x(G,v\leftarrow n,\beta)$ in
terms of the variables $x^{i}(\bar{n}_{i})$, which represent the probability
distribution over the assignments of adjacent vertices in smaller graphs. We
will again assume that the vertex $v$ has $d\leq\Delta$ neighbors
$v_{1},\ldots v_{d}$. We start this process by proving the next two Lemmas.

######  Lemma 3 (Recursive Deconstruction).

$\displaystyle x(G,v\leftarrow n,\beta)=$ $\displaystyle x(G,v\leftarrow
0,\beta)\sum\limits_{n_{1},\ldots n_{d}\in S_{n}}x(\bar{n}_{1})\ldots
x(\bar{n}_{d})$

###### Proof.

Notice that

$Z(G,(\beta,v\leftarrow 0))=Z(G\setminus v,\beta),$

and more generally

$Z(G,(\beta,v\leftarrow n))=\sum\limits_{(n_{1},...n_{d})\in
S_{n}^{d}}Z(G\setminus v,(\beta,(v_{i}\leftarrow n_{i}\forall i))).$

Using this, we have

$\displaystyle x(G,v\leftarrow n,\beta)$
$\displaystyle=\frac{Z(G,(\beta,v\leftarrow n))}{Z(G,\beta)}$
$\displaystyle=\frac{Z(G,(\beta,v\leftarrow 0))Z(G,(\beta,v\leftarrow
n))}{Z(G,\beta)Z(G\setminus v,\beta)}$ $\displaystyle=\frac{x(G,v\leftarrow
0,\beta)}{Z(G\setminus v,\beta)}Z(G,(\beta,v\leftarrow n))$
$\displaystyle=\frac{x(G,v\leftarrow 0,\beta)}{Z(G\setminus
v,\beta)}\sum\limits_{(n_{1},...n_{d})\in S_{n}^{d}}Z(G\setminus
v,(\beta,(v_{i}\leftarrow n_{i}\forall i)))$
$\displaystyle=\frac{x(G,v\leftarrow 0,\beta)}{Z(G\setminus
v,\beta)}\sum\limits_{n_{1}\in S_{n}}Z(G\setminus v,(\beta,v_{1}\leftarrow
n_{1}))\sum\limits_{(n_{2},...n_{d})\in S_{n}^{d-1}}\frac{Z(G\setminus
v,(\beta,(v_{i}\leftarrow n_{i}\forall i)))}{Z(G\setminus
v,(\beta,v_{1}\leftarrow n_{1}))}$ $\displaystyle=x(G,v\leftarrow
0,\beta)\sum\limits_{n_{1}\in S_{n}}{Z(G\setminus v,(\beta,v_{1}\leftarrow
n_{1}))\over Z(G\setminus v,\beta)}\sum\limits_{(n_{2},...n_{d})\in
S_{n}^{d-1}}\frac{Z(G\setminus v,(\beta,(v_{i}\leftarrow n_{i}\forall
i)))}{Z(G\setminus v,(\beta,v_{1}\leftarrow n_{1}))}$
$\displaystyle=x(G,v\leftarrow 0,\beta)\sum\limits_{n_{1}\in
S_{n}}x(G\setminus v,v_{1}\leftarrow
n_{1},\beta)\sum\limits_{(n_{2},...n_{d})\in S_{n}^{d-1}}\frac{Z(G\setminus
v,(\beta,(v_{i}\leftarrow n_{i}\forall i)))}{Z(G\setminus
v,(\beta,v_{1}\leftarrow n_{1}))}$ $\displaystyle=x(G,v\leftarrow
0,\beta)\sum\limits_{n_{1}\in
S_{n}}x(\bar{n}_{1})\sum\limits_{(n_{2},...n_{d})\in
S_{n}^{d-1}}\frac{Z(G\setminus v,(\beta,(v_{i}\leftarrow n_{i}\forall
i)))}{Z(G\setminus v,(\beta,v_{1}\leftarrow n_{1}))}$
$\displaystyle=x(G,v\leftarrow 0,\beta)\sum\limits_{n_{1}\in
S_{n}}x(\bar{n}_{1})\ldots\sum\limits_{n_{d}\in S_{n}}x(\bar{n}_{d})$
$\displaystyle=x(G,v\leftarrow 0,\beta)\sum\limits_{n_{1},\ldots n_{d}\in
S_{n}}x(\bar{n}_{1})\ldots x(\bar{n}_{d}),$

where the second to last line is derived by repeating the same logic for each
neighbor $v_{i}$ with a, appropriately modified value of $\beta$. ∎

######  Lemma 4 (Normalizing Term).

$x(G,v\leftarrow
0,\beta)=\frac{1}{\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{m}}x(\bar{n}_{1})\ldots x(\bar{n}_{d})}.$

###### Proof.

By construction, $\sum\limits_{m=0}^{(1-\alpha)N}x(G,v\leftarrow m,\beta)=1$,
since $((x(G,v\leftarrow m,\beta))$ is a probability vector for
$m\in[0,(1-\alpha)N]$. Thus, by Lemma 3,

$\displaystyle 1=\sum\limits_{m=0}^{(1-\alpha)N}x(G,v\leftarrow
m,\beta)=x(G,v\leftarrow
0,\beta)\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots n_{d}\in
S_{m}}x(\bar{n}_{1})\ldots x(\bar{n}_{d}).$

Rearranging terms, we have

$x(G,v\leftarrow
0,\beta)=\frac{1}{\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{m}}x(\bar{n}_{1})\ldots x(\bar{n}_{d})}.$

∎

Combining Lemmas 3 and 4, we immediately obtain Proposition 2.

###  3.2 Bounds on Marginal Probabilities

Section 4 will be dedicated to establishing a bound on the 1-norm of the
function $f_{n}$ from equation 3. The bound we compute will need to hold not
just on the true probability distribution x, but also on any linear
interpolation between the true distribution and our probability estimates. To
do this, we identify the primary properties we need for the contraction to
hold. Thus, we introduce the following notion of a Feasible Marginal
Distribution, and show that our bound will hold on all such distributions.

######  Definition 1 (Feasible Marginal Distribution).

Fix some $\textbf{w}=\\{w_{k}>0,0\leq k\leq(1-\alpha)N\\}$. We say that w is a
Feasible Probability Distribution if

$\displaystyle\sum\limits_{k=0}^{(1-\alpha)N}w_{k}$ $\displaystyle=1,$ (4)
$\displaystyle w_{k}$ $\displaystyle\geq w_{k+1},$ (5) $\displaystyle w_{k}$
$\displaystyle=w_{k^{\prime}}$ $\displaystyle\forall k,k^{\prime}\leq\alpha
N.$ (6)

Further, we say $\textbf{y}=\\{y^{j}(\bar{n}_{j})|j\in\\{1,\ldots
d\\},\bar{n}_{j}\in[0,(1-\alpha)N]^{j}\\}$ is a Feasible Marginal Distribution
if for every $j\in\\{1,\ldots d\\}$ and
$\bar{n}_{j-1}\in[0,(1-\alpha)N]^{j-1}$ where $(\beta,v_{i}\leftarrow
n_{i},i<j)$ forms a feasible set of constraints, the values
$y_{i}=y^{j}(\bar{n}_{j-1},i)$ for $i\in[0,(1-\alpha)N]$ form a Feasible
Probability Distribution and for every $\bar{n}_{j},\bar{m}_{j}\in[0,\alpha
N]$,

$y^{j}(\bar{n}_{j})=y^{j}(\bar{m}_{j}).$

We now show that x as defined above is a Feasible Marginal Distribution.
Firstly, observe from the problem’s construction that for any fixed
$j,n_{1},\ldots n_{j-1}$, the set
$\\{x^{j}(\bar{n}_{j-1},n_{j})|n_{j}\in[0,(1-\alpha)N]\\}$ forms a probability
distribution when $(\beta,v_{i}\leftarrow n_{i},i<j)$ forms a feasible set of
constraints, meaning equation 4 is satisfied. Next, notice that
$Z(G,(\beta,v\leftarrow n))\geq Z(G,(\beta,v\leftarrow n+1))$, since for every
relaxed independent set where $v$ is assigned $n+1$ there is a relaxed in
dependent that is identical except $v$ is assigned $n$. Thus, we have that for
every fixed $\bar{n}_{j-1}$, $x(\bar{n}_{j-1},n_{j})\geq
x(\bar{n}_{j-1},n_{j}+1)$, so x satisfies equation 5. Finally, we have that
$Z(G,(\beta,v\leftarrow n))=Z(G,(\beta,v\leftarrow n^{\prime}))$ for every
$0\leq n,n^{\prime}\leq\alpha N$, since assigning any vertex a value in
$[0,\alpha N]$ cannot violate any constraints. More generally, if every
constraint in $\beta$ and $\beta^{\prime}$ assigns a value of at most $\alpha
N$, then $Z(G,\beta)=Z(G,\beta^{\prime})$. This implies x must satisfy
equations 6 and 1. Therefore, x is a Feasible Marginal Distribution.

######  Lemma 5 (Closure of Feasible Marginal Distributions under $f_{n}$).

Let y be a Feasible Marginal Distribution, and let
$y_{n}^{\prime}=f_{n}(\textbf{y})$ for $n\in[0,(1-\alpha)N]$. Then, the set of
$y_{n}^{\prime}$ form a Feasible Probability Distribution.

###### Proof.

Notice that $S_{n}=S_{n^{\prime}}$ for any $n,n^{\prime}\leq\alpha N$ by
construction. By equation 3, we can clearly see this implies
$f_{n}(\textbf{y})=f_{n^{\prime}}(\textbf{y})$ when $n,n^{\prime}\leq\alpha
N$, so the values of $y_{n}^{\prime}$ satisfy equation 6. Equation 4 is
satisfied because

$\sum\limits_{n=0}^{(1-\alpha)N}f_{n}(\textbf{y})=\frac{\sum\limits_{n=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{n}}x^{1}(\bar{n}_{1})\ldots
x^{d}(\bar{n}_{d})}{\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{m}}x^{1}(\bar{n}_{1})\ldots x^{d}(\bar{n}_{d})}=1.$

Finally, equation 5 is clearly satisfied because $S_{n}$ is non-increasing in
$n$ and each term in the numerator sum is non-negative. ∎

######  Lemma 6 (Linear Interpolations of Feasible Marginal Distributions).

Let y and z be two Feasible Marginal Distributions. Then, for any $w\in[0,1]$,
$w\textbf{y}+(1-w)\textbf{z}$ is a Feasible Marginal Distribution, where the
sum is taken pointwise.

The proof of Lemma 6 follows directly from the linearity of the four equations
4, 5, 6, and 1. These results will allow us to construct the contraction in
sufficient generality. We conclude by proving two Lemmas about Feasible
Probability Distributions.

######  Lemma 7.

For any Feasible Probability Distribution y, we have

$y_{i}\leq\frac{1}{\alpha N}.$

###### Proof.

By equation 6, for any $i,j\in[0,\alpha N]$, the value of $y_{i}=y_{j}$. There
are $\alpha N$ such values, so each one must be no greater than
$\frac{1}{\alpha N}$. Additionally, for any $i$, $y_{i}\leq
y_{0}\leq\frac{1}{\alpha N}$ by equation 5, finishing the proof. ∎

######  Lemma 8.

For any Feasible Probability Distribution y, we have

$\frac{\alpha}{1-\alpha}\leq\sum_{i=0}^{\alpha N}y_{i}\leq 1.$

###### Proof.

The upper bound holds directly from equation 4. To prove the lower bound,
first observe equation 4 implies $\sum\limits_{i=0}^{(1-\alpha)N}y_{i}=1$. If
$\sum\limits_{i=0}^{\alpha N}y_{i}<\frac{\alpha}{1-\alpha}$, then it would
have to be the case that $\sum\limits_{i=\alpha
N+1}^{(1-\alpha)N}y_{i}>\frac{1-2\alpha}{1-\alpha}$. This would imply the last
$1-2\alpha$ terms in the sequence had a larger average value than the first
$\alpha$ terms. Equation 5 implies this sequence must be decreasing, which is
a contradiction. Thus, the bound must hold.

∎

##  4 Proof of the Correlation Decay Property

In this section, we establish the key correlation decay property necessary to
design the approximation algorithm. The primary result, occurring at the end
of the section, will be a bound on $\|f_{n}(\textbf{y})\|_{1}$ defined in
equation 3 with respect to a vertex $v$ with $d$ neighbors for any Feasible
Marginal Distribution y. The bound will be in terms of $\alpha$ and $d$, and
will be bounded away from 1 as $\alpha$ approaches $1/2$ for any fixed $d$.

###  4.1 Expressions for Partial Derivatives

We now introduce the following two expressions to represent the numerator and
denominator of equation 3:

$\displaystyle U_{n}$ $\displaystyle=\sum\limits_{n_{1},\ldots n_{d}\in
S_{n}}y^{1}(\bar{n}_{1})\ldots y^{d}(\bar{n}_{d}),$ $\displaystyle L$
$\displaystyle=\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in
S_{m}}y^{1}(\bar{n}_{1})y^{d}(\bar{n}_{d})=\sum\limits_{m=0}^{(1-\alpha)N}U_{m}.$

In particular, we have that $f_{n}(\textbf{y})=\frac{U_{n}}{L}$. By the chain
rule, we can see

$\frac{\partial f_{n}(\textbf{y})}{\partial
y^{j}(\bar{n}_{j})}=\frac{L\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})}-U_{n}\frac{\partial L}{\partial
x^{j}(\bar{n}_{j})}}{L^{2}}.$

Let

$\displaystyle B_{j}(\bar{n}_{j-1})$ $\displaystyle=y^{1}(\bar{n}_{1})\ldots
y^{j-1}(\bar{n}_{j-1}),$ $\displaystyle A_{j}(n,\bar{n}_{j})$
$\displaystyle=\sum\limits_{n_{j+1},\ldots n_{d}\in
S_{n}}y^{j+1}(\bar{n}_{j+1})\ldots y^{d}(\bar{n}_{d}).$

Thus, for any $j\in[1,d]$, we have

$\displaystyle U_{n}$ $\displaystyle=\sum\limits_{n_{1},\ldots n_{j-1}\in
S_{n}}B_{j}(\bar{n}_{j-1})\sum\limits_{n_{j}\in
S_{n}}y^{j}(\bar{n}_{j})A_{j}(n,\bar{n}_{j}),$ (9) $\displaystyle L$
$\displaystyle=\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{j-1}\in S_{m}}B_{j}(\bar{n}_{j-1})\sum\limits_{n_{j}\in
S_{m}}y^{j}(\bar{n}_{j})A_{j}(m,\bar{n}_{j}).$ (10)

Fix $j\in[1,d]$ and some $\bar{n}_{j}\in[0,(1-\alpha)N]^{j}$. Letting $I(A)$
be the indicator variable for the event $A$, we obtain

$\displaystyle\frac{\partial U_{n}}{\partial x^{j}(\bar{n}_{j})}$
$\displaystyle=I(\bar{n}_{j}\in
S_{n}^{d})B_{j}(\bar{n}_{j-1})A_{j}(n,\bar{n}_{j}),$ (11)
$\displaystyle\frac{\partial L}{\partial x^{j}(\bar{n}_{j})}$
$\displaystyle=\sum\limits_{m=0}^{(1-\alpha)N}I(\bar{n}_{j}\in
S_{m}^{d})B_{j}(\bar{n}_{j-1})A_{j}(m,\bar{n}_{j}).$ (12)

######  Lemma 9.

For any $j\in[1,d]$, $n\in[0,(1-\alpha)N]$, and $n_{1},\ldots
n_{j}\in[0,(1-\alpha)N]$, we have

$\displaystyle A_{j}(n,\bar{n}_{j})$ $\displaystyle\leq 1,$ $\displaystyle
B_{j}(\bar{n}_{j-1})$ $\displaystyle\leq\frac{1}{(\alpha N)^{j-1}}.$

###### Proof.

Recall that for any $\bar{n}_{d-1}$, $y_{d}(\bar{n}_{d})$ is a probability
distribution as $n_{d}$ varies. Thus,

$\sum\limits_{n_{d}\in
S_{n}}y_{d}(\bar{n}_{d})\leq\sum\limits_{n_{d}=0}^{(1-\alpha)N}y_{d}(\bar{n}_{d})=1.$

Iterating this process for vertices $v_{d},v_{d-1},\ldots v_{j+1}$ leads to
the bound on $A_{j}$. The bound on $B_{j}$ follows from Lemma 7. ∎

######  Lemma 10.

For any $j\in[1,d]$, $n\in[0,(1-\alpha)N]$, $n_{1},\ldots n_{j}\in[0,\alpha
N]$, and $m_{1},\ldots m_{j}\in[0,\alpha N]$ we have that

$\displaystyle A_{j}(n,\bar{n}_{j})$ $\displaystyle=A_{j}(n,\bar{m}_{j})$
$\displaystyle B_{j}(\bar{n}_{j-1})$ $\displaystyle=B_{j}(\bar{m}_{j-1})$

###### Proof.

By definition, we have
$y^{j^{\prime}}(\bar{n}_{j^{\prime}})=y^{j^{\prime}}(\bar{m}_{j^{\prime}})$
for any $j^{\prime}\leq j$. Repeatedly substituting these equalities into the
definitions of $A_{j}$ and $B_{j}$ produces the desired result. ∎

We now move to bounding our numerator and denominator functions, $U_{n}$ and
$L$, directly.

######  Lemma 11 (Gradient Denominator).

$L\geq\alpha N$

###### Proof.

Fix any $m\leq\alpha N$. We will have that
$S_{m}=[0,\min(N-m,(1-\alpha)N]=[0,(1-\alpha)N]$. For any $n_{1},\ldots
n_{j-1}$, $\sum\limits_{n_{j}=0}^{\alpha N}y^{j}(\bar{n}_{j})=1$ since y is a
Feasible Marginal Distribution. Thus,

$\displaystyle\sum\limits_{n_{1},\ldots n_{d}\in
S_{m}}y^{1}(\bar{n}_{1})\ldots y^{d}(\bar{n}_{d})=\sum\limits_{n_{1},\ldots
n_{d}=0}^{(1-\alpha)N}y^{1}(\bar{n}_{1})\ldots y^{d}(\bar{n}_{d})=1.$

We then obtain

$\displaystyle L=\sum\limits_{m=0}^{(1-\alpha)N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{m}}y^{1}(\bar{n}_{1})\ldots
y^{d}(\bar{n}_{d})\geq\sum\limits_{m=0}^{\alpha N}\sum\limits_{n_{1},\ldots
n_{d}\in S_{m}}y^{1}(\bar{n}_{1})\ldots
y^{d}(\bar{n}_{d})=\sum\limits_{m=0}^{\alpha N}1=\alpha N.$

∎

######  Lemma 12 (Upper bounds).

For any $j\in[1,d]$, $n\in[0,(1-\alpha)N]$, and $n_{1},\ldots
n_{j-1}\in[0,(1-\alpha)N]$, we have

$\displaystyle U_{n}$ $\displaystyle\leq 1,$ $\displaystyle L$
$\displaystyle\leq(1-\alpha)N,$ $\displaystyle\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})}$ $\displaystyle\leq\frac{1}{(\alpha N)^{j-1}},$
$\displaystyle\frac{\partial L}{\partial x^{j}(\bar{n}_{j})}$
$\displaystyle\leq\frac{(1-\alpha)N}{(\alpha N)^{j-1}}.$

###### Proof.

We will show the bounds on $U_{n}$ and $\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})}$. These will immediately imply the bounds on $L$ and
$\frac{\partial L}{\partial x^{j}(\bar{n}_{j})}$ by definition. Writing
$U_{n}$ in terms of $A_{1}$ in equation 9, we see that

$\displaystyle U_{n}=\sum\limits_{n_{1}\in
S_{n}}y^{j}(\bar{n}_{1})A_{1}(n,\bar{n}_{1})\leq\sum\limits_{n_{1}\in
S_{n}}y^{j}(\bar{n}_{1})\leq 1,$

where the first inequality follows from Lemma 9 and the second follows from
equation 4. Similarly, we can write $\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})}$ in terms of $A_{j}$ and $B_{j}$ as in equation 11 to see
that

$\frac{\partial U_{n}}{\partial x^{j}(\bar{n}_{j})}=I(\bar{n}_{j}\in
S_{n}^{d})B_{j}(\bar{n}_{j-1})A_{j}(n,\bar{n}_{j})\leq
B_{j}(\bar{n}_{j-1})A_{j}(n,\bar{n}_{j})\leq\frac{1}{(\alpha N)^{j}},$

where the last inequality follows from Lemma 9.

∎

###  4.2 Upper Bounds on Partial Derivatives

We are now obtain bounds on the value of the partial derivatives of
$f(\textbf{y})$, in order to ultimately bound $\|\nabla f(\textbf{y})\|_{1}$.
We will do this by using two different bounds on $\frac{\partial
f(\textbf{y})}{\partial y^{j}(\bar{n}_{j})}$, depending on the value of
$\bar{n}_{j}$. We present the looser bound first, which applies to all partial
derivatives.

######  Theorem 13 (Loose Partial Bound).

For any $j\in[1,d]$ and $\bar{n}_{j}\in[0,(1-\alpha)N]^{j}$,

$\left|\frac{\partial f(\textbf{y})}{\partial
y^{j}(\bar{n}_{j})}\right|\leq\frac{(1-\alpha)N}{(\alpha N)^{j+1}}$

###### Proof.

As we saw in equation 4.1, we have

$\displaystyle\left|\frac{\partial f(\textbf{y})}{\partial
y^{j}(\bar{n}_{j})}\right|$ $\displaystyle=\left|\frac{L\frac{\partial
U_{n}}{\partial x^{j}(\bar{n}_{j})}-U_{n}\frac{\partial L}{\partial
x^{j}(\bar{n}_{j})}}{L^{2}}\right|$
$\displaystyle\leq\frac{\max(L\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})},U_{n}\frac{\partial L}{\partial
x^{j}(\bar{n}_{j})}}{L^{2}}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{a}}}}{{\leq}}\frac{\max(L\frac{\partial
U_{n}}{\partial x^{j}(\bar{n}_{j})},U_{n}\frac{\partial L}{\partial
x^{j}(\bar{n}_{j})})}{(\alpha N)^{2}}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{b}}}}{{\leq}}\frac{(1-\alpha)N}{(\alpha
N)^{j+1}},$

where inequality a follows from Lemma 11 and inequality b follows from Lemma
12. ∎

As we will see in the next section, this bound alone will not be sufficiently
tight. Next, we introduce a tighter bound on the partial derivative for cases
where $\bar{n}_{j}\in[0,\alpha N]^{j}$.

######  Theorem 14 (Tighter Partial Bound).

For any $j\in[1,d]$ and $\bar{n}_{j}\in[0,\alpha N]^{j}$,

$\left|\frac{\partial f(\textbf{y})}{\partial
y_{j}(\bar{n}_{j})}\right|\leq\frac{j(1-2\alpha)(1-\alpha)^{j}}{\alpha^{2j+1}N^{j}}.$

###### Proof.

$\displaystyle\left|\frac{\partial f(\textbf{y})}{\partial
y_{j}(\bar{n}_{j})}\right|$ $\displaystyle=\frac{|L\frac{\partial
U_{n}}{\partial x^{j}(\bar{n}_{j})}-U_{n}\frac{\partial L}{\partial
x^{j}(\bar{n}_{j})}|}{L^{2}}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{a}}}}{{\leq}}\frac{1}{(\alpha
N)^{2}}|L\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})}-U_{n}\frac{\partial L}{\partial x^{j}(\bar{n}_{j})}|$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{b}}}}{{=}}\frac{1}{(\alpha
N)^{2}}\left|\sum\limits_{m=0}^{(1-\alpha)N}\left[\sum\limits_{\bar{m}_{j}\in
S_{m}^{j}}\frac{\partial U_{n}}{\partial
x^{j}(\bar{n}_{j})}B_{j}(\bar{m}_{j-1})y^{j}(\bar{m}_{j})A_{j}(m,\bar{m}_{j})-U_{n}I(\bar{n}_{j}\in
S_{m}^{j})B_{j}(\bar{n}_{j-1})A_{j}(m,\bar{n}_{j})\right]\right|$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{c}}}}{{=}}\frac{1}{(\alpha
N)^{2}}\Bigg{|}\sum\limits_{m=0}^{(1-\alpha)N}\Bigg{[}\sum\limits_{\bar{m}_{j}\in
S_{m}^{j}}I(\bar{n}_{j}\in
S_{n}^{j})B_{j}(\bar{n}_{j-1})A_{j}(n,\bar{n}_{j})B_{j}(\bar{m}_{j-1})y^{j}(\bar{m}_{j})A_{j}(m,\bar{m}_{j})$
$\displaystyle-\sum\limits_{\bar{p}_{j}\in
S_{n}^{j}}B_{j}(\bar{p}_{j-1})y^{j}(\bar{p}_{j})A_{j}(n,\bar{p}_{j})I(\bar{n}_{j}\in
S_{m}^{j})B_{j}(\bar{n}_{j-1})A_{j}(m,\bar{n}_{j})\Bigg{]}\Bigg{|}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{d}}}}{{=}}\frac{B_{j}(\bar{n}_{j-1})}{(\alpha
N)^{2}}\Bigg{|}\sum\limits_{m=0}^{(1-\alpha)N}\Bigg{[}\sum\limits_{\bar{m}_{j}\in
S_{m}^{j}}\bigg{\\{}A_{j}(n,\bar{n}_{j})B_{j}(\bar{m}_{j-1})y^{j}(\bar{m}_{j})A_{j}(m,\bar{m}_{j})\bigg{\\}}$
$\displaystyle-\sum\limits_{\bar{p}_{j}\in
S_{n}^{j}}\bigg{(}B_{j}(\bar{p}_{j-1})y^{j}(\bar{p}_{j})A_{j}(n,\bar{p}_{j})A_{j}(m,\bar{n}_{j})\bigg{)}\Bigg{]}\Bigg{|}$

where inequality a comes from Lemma 11, and equalities b and c come from
applying equations 10, 12, 9, and 11. Equality d comes from factoring out
$B_{j}(\bar{n}_{j-1})$ and observing that $\bar{n}_{j}\in S_{n}^{j},S_{m}^{j}$
because we assumed it was in $[0,\alpha N]^{j}$, which is a subset of $S_{k}$
for every $k$.

We observe that when $\bar{m}_{j},\bar{p}_{j}\in[0,\alpha N]^{j}$, the
expression above in the braces $\\{\\}$ will be equal to the expression in the
parentheses $()$ by Lemma 10 and equation 1. Additionally, we bound the
expression in the braces $\\{\\}$. Using Lemmas 7 and 9, we have that for any
$\bar{m}_{j}$

$A_{j}(n,\bar{n}_{j})B_{j}(\bar{m}_{j-1})y^{j}(\bar{m}_{j})A_{j}(m,\bar{m}_{j})\leq\frac{1}{(\alpha
N)^{j}},$

with the same bound being true for the expression in the parentheses $()$.
Thus, we see

$\displaystyle\left|\frac{\partial f(\textbf{y})}{\partial
y_{j}(\bar{n}_{j})}\right|\leq$
$\displaystyle\frac{B_{j}(\bar{n}_{j-1})}{(\alpha
N)^{2}}\sum\limits_{m=0}^{(1-\alpha)N}\Bigg{[}\max\Bigg{(}\sum\limits_{\bar{m}_{j}\in
S_{m}^{j},\bar{m}_{j}\not\in[0,\alpha
N]^{j}}A_{j}(n,\bar{n}_{j})B_{j}(\bar{m}_{j-1})y^{j}(\bar{m}_{j})A_{j}(m,\bar{m}_{j}),$
$\displaystyle\sum\limits_{\bar{p}_{j}\in
S_{n}^{j},\bar{p}_{j}\not\in[0,\alpha
N]^{j}}B_{j}(\bar{p}_{j-1})y^{j}(\bar{p}_{j})A_{j}(n,\bar{p}_{j})A_{j}(m,\bar{n}_{j})\Bigg{)}\Bigg{]}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{a}}}}{{\leq}}$
$\displaystyle\frac{B_{j}(\bar{n}_{j-1})}{(\alpha
N)^{2}}\sum\limits_{m=0}^{(1-\alpha)N}\frac{N^{j}[(1-\alpha)^{j}-\alpha^{j}]}{(\alpha
N)^{j}}$ $\displaystyle\stackrel{{\scriptstyle\mathclap{\mbox{b}}}}{{\leq}}$
$\displaystyle\frac{1}{(\alpha
N)^{j+1}}\sum\limits_{m=0}^{(1-\alpha)N}\frac{N^{j}[(1-\alpha)^{j}-\alpha^{j}]}{(\alpha
N)^{j}}$ $\displaystyle=$ $\displaystyle\frac{(1-\alpha)N}{(\alpha
N)^{j+1}}\left(\frac{(1-\alpha)^{j}}{\alpha^{j}}-1\right)$

Inequality b comes from Lemma 9. Inequality a comes from the bound above, and
observing that there are at most $N^{j}(1-\alpha)^{j}$ vectors in $S_{m}^{j}$
or $S_{n}^{j}$ and exactly $N^{j}\alpha^{j}$ vectors in $[0,\alpha N]^{j}$. ∎

###  4.3 Bounding the Gradient

We are now able to prove a bound on the gradient of the function in equation 3
in terms of $d$ and $\alpha$.

######  Theorem 15 (Bounded Gradient).

For any $n\in[0,(1-\alpha)N]$,

$\|\nabla
f_{n}(\textbf{y})\|_{1}\leq\frac{2d(1-\alpha)}{\alpha}\left(\frac{(1-\alpha)^{d}}{\alpha^{d}}-1\right).$

In particular, when $G$ has maximum degree $\Delta$, $\|\nabla
f_{n}(\textbf{y})\|_{1}<1$ so long as $\alpha>\alpha_{\Delta}$, where
$\alpha_{\Delta}$ is defined in equation  ‣ 2.

###### Proof.

First, fix some $j\in[1,d]$. Notice that there are exactly $(\alpha N)^{j}$
different $\bar{n}_{j}\in[0,\alpha N]^{j}$. Further, there are
$(1-\alpha)^{j}N^{j}$ different $\bar{n}_{j}\in[0,(1-\alpha)N]^{j}$, meaning
there are $N^{j}[(1-\alpha)^{j}-\alpha^{j}]$ vectors in the latter not in the
former.

Using theorems 13 and 14, we obtain

$\displaystyle\sum\limits_{\bar{n}_{j}\in[0,(1-\alpha)N]^{j}}\left|\frac{\partial
f(\textbf{y})}{\partial y^{j}(\bar{n}_{j})}\right|$ $\displaystyle\leq(\alpha
N)^{j}\frac{(1-\alpha)N}{(\alpha
N)^{j+1}}\left(\frac{(1-\alpha)^{j}}{\alpha^{j}}-1\right)+N^{j}((1-\alpha)^{j}-\alpha^{j})\frac{(1-\alpha)N}{(\alpha
N)^{j+1}}$
$\displaystyle=\frac{2(1-\alpha)}{\alpha}\left(\frac{(1-\alpha)^{j}}{\alpha^{j}}-1\right).$

Using this, we can conclude

$\displaystyle\|\nabla f_{n}(\textbf{y})\|_{1}$
$\displaystyle=\sum\limits_{j=1}^{d}\sum\limits_{\bar{n}_{j}\in[0,(1-\alpha)N]^{j}}\left|\frac{\partial
f(\textbf{y})}{\partial y^{j}(\bar{n}_{j})}\right|$
$\displaystyle\leq\sum\limits_{j=1}^{d}\frac{2(1-\alpha)}{\alpha}\left(\frac{(1-\alpha)^{j}}{\alpha^{j}}-1\right)$
$\displaystyle\leq\sum\limits_{j=1}^{d}\frac{2(1-\alpha)}{\alpha}\left(\frac{(1-\alpha)^{d}}{\alpha^{d}}-1\right)$
$\displaystyle=\frac{2d(1-\alpha)}{\alpha}\left(\frac{(1-\alpha)^{d}}{\alpha^{d}}-1\right).$

∎

Evaluated at $\Delta=3$, we obtain $\alpha_{3}\approx 0.488$. Take
$\alpha=0.5-c/\Delta^{\gamma}$, with $c$ a constant not dependent on $\Delta$
and $\gamma>0$. When $\gamma<2$, we have

$\lim_{\Delta\rightarrow\infty}\frac{2\Delta(0.5+c/\Delta^{\gamma})}{(0.5-c/\Delta)^{\gamma}}\left(\frac{(0.5+c/\Delta^{\gamma})^{\Delta}}{(0.5-c/\Delta^{\gamma})^{\Delta}}-1\right)=\infty.$

But, when $\gamma=2$ and $c<\frac{1}{8}$, we have

$\lim_{\Delta\rightarrow\infty}\frac{2\Delta(0.5+c/\Delta^{2})}{(0.5-c/\Delta)^{2}}\left(\frac{(0.5+c/\Delta^{2})^{\Delta}}{(0.5-c/\Delta^{2})^{\Delta}}-1\right)=8c<1.$

Thus, $\alpha_{\Delta}$ is of the form $0.5-O(1/\Delta^{2})$.

##  5 A Counting Algorithm

In this section, we design an algorithm to approximate $Z(G)$. We first
demonstrate how to use the contraction proven in Section 4 to design a
recursive algorithm which approximates $x(G,v\leftarrow n,\beta)$ with error
decaying geometrically in the recursion depth. With this, we will present the
approximation algorithm and formalize the argument from Section 2.

Algorithm 1 ApproxProb

1:Input

2: $G=(V,E)$Bounded degree Graph with at least 1 vertex

3: $k$Remaining Computation Depth

4: $v$Vertex in the graph $G$

5: $\alpha$Value in $[0,0.5)$

6: $n^{*}$Integer value to assign vertex $v$

7: $N$Positive Integer

8: $\beta$Set of constraints for the vertices $V$, with $\beta_{v}$ denoting
the assigned value

9:Output

10: $\tilde{f}_{n}(\textbf{x})$Estimate of $f_{n}(\textbf{x})$, probability
vertex $v$ is assigned $n^{*}$ in the Gibbs distribution

11:Let $b=\max\\{\beta_{u_{i}}\\}$, where $u_{i}$ is the set of constrained
neighbors of $v$

12:if $n^{*}>N-b$ then Return 0

13:else if $\exists$ constrained adjacent vertices $u_{1},u_{2}$ with
$\beta_{u_{1}}+\beta_{u_{2}}>N$ then Return $0$

14:else if $k=0$ then Return $\frac{1}{\min\\{(1-\alpha)N+1,N-b+1\\}}$

15:else

16: Let $d$ be the number of unconstrained neighbors $v$ has, and let
$v_{1},\ldots v_{d}$ be those neighbors

17: for $j\in[1,d]$ do

18: for $n_{1},\ldots n_{j}\in[0,(1-\alpha)N]$ do

19: Let $y^{j}(\bar{n}_{j})=\operatorname{ApproxProb}(G\setminus
v,k-1,v_{j},\alpha,n_{i},N,(\beta,v_{i}\leftarrow n_{i},\forall i<j))$

20: end for

21: end for

22: Return $f_{n}(\textbf{y})$

23:end if

###  5.1 Approximating Probabilities

In this section, we introduce Algorithm 1, ApproxProb. This algorithm
recursively computes an approximation $y(G,v\leftarrow n,\beta)$ of
$x(G,v\leftarrow n,\beta)$.

######  Lemma 16.

Take some arbitrary graph $G$ with degree bounded by $\Delta$, as well as some
parameters $N,\alpha,\beta$ satisfying $\|\nabla f^{v}_{n}\|_{1}=c<1$, where
$f^{v}_{n}$ is the function from equation 3, for each vertex $v$ in every
subgraph of $G$ with any $\beta$ for the particular values of $N$ and
$\alpha$. Pick any computation depth $k>0$. Algorithm 1 called with parameters
$G,k,\alpha,N,$ and $\beta$ will produce an approximation $y=y(G,v\leftarrow
n^{*},\beta)$ of $x=x(G,v\leftarrow n^{*},\beta)$ satisfying

$|y-x|\leq c^{k}.$

Further, it will do so in time $N^{O(k\Delta)}$.

###### Proof.

We will first need to establish that the estimated marginal probabilities y
computed on line 19 form a Feasible Marginal Distribution. We will do so
inductively, starting with $k=1$, as it is the first time we compute such a y.
When $k=1$, y will form a Feasible Marginal Distribution by construction. The
Feasible Probability Distribution requirements will be satisfied by the value
returned on line 14, since it will be the uniform probability measure over all
feasible values of $n^{*}$. Further, for any $j\in\\{1,\ldots d\\}$ and
$\bar{n}_{j},\bar{m}_{j}\in[0,\alpha N]^{j}$,
$y^{j}(\bar{n}_{j})=y^{j}(\bar{m}_{j})=\frac{1}{(1-\alpha)N}$, satisfying the
final requirement.

Proceeding by induction for $k>1$, we have that the Feasible Probability
Distribution requirements will be satisfied by Lemma 5 and the inductive
hypothesis. Additionally, observe that if $n,m\leq\alpha N$, changing
$u\leftarrow n$ to $u\leftarrow m$ in a constraint set $\beta$ will not change
the result of running ApproxProb. This is because $u$ assigned to either value
cannot violate any constraints. Finally, notice that the vector y computed in
a call to ApproxProb does not depend on $n^{*}$, and $f_{n}=f_{m}$ for any
$n,m\leq\alpha N$. Thus, the vector y computed on line 19 must satisfy
equation 1, so y is a Feasible Marginal Distribution.

We will now show the main result via induction. For the base case, suppose
that $k=1$. Let x be the true values of the variables $x(\bar{n}_{i})$
according to the Gibbs distribution of their corresponding graphs. Let y be
the values of the variables computed in the execution of the algorithm on line
19. By the mean value theorem, there must exists some z, which is a linear
interpolation of y and x such that

$f_{n}^{v}(\textbf{x})-f_{n}^{v}(\textbf{y})=\nabla
f^{v}_{n}(\textbf{z})\cdot(\textbf{x}-\textbf{y}).$

By Lemma 6, z must also be a Feasible Marginal Distribution. Further, every
entry in x and y is non-negative and bounded by 1. Thus,

$|f_{n}^{v}(\textbf{x})-f_{n}^{v}(\textbf{y})|\leq\|\nabla
f^{v}_{n}(\textbf{z})\|_{1}\|\textbf{x}-\textbf{y}\|_{\infty}\leq c.$

We now induct over the values of $k$. Once again, let x be the true values of
the variables $x(\bar{n}_{i})$, and let y be the values computed on line 19
during the outermost layer of the recursion. Notice that any entries of y
which are 0 will also be 0 in x. This, combined with the inductive hypothesis,
implies that $\|\textbf{x}-\textbf{y}\|_{\infty}\leq c^{k-1}$. Thus, using the
same logic as above, we can use the mean value theorem to show that
$|f^{v}_{n}(\textbf{x})-f^{v}_{n}(\textbf{y})\|\leq c^{k}$ as desired.

Additionally, we wish to analyze the runtime of Algorithm 1. Let $T(k)$ denote
the runtime of the algorithm with the input $k$, and notice that $T(0)=O(1)$.
For runs with higher values of $k$, the limiting time step will be computing
the recursive calls on line 20. There will be at most
$(1-\alpha)^{\Delta}N^{\Delta}$ iterations, and each will take $O(\Delta^{2})$
time to update the values of $\beta$. Therefore, we get that
$T(k)=O((1-\alpha)^{\Delta}N^{\Delta}\Delta^{2}T(k-1))$ implying that
$T(k)=O\left(\left((1-\alpha)^{\Delta}N^{\Delta}\Delta^{2}\right)^{k}\right)$.
Since we are interested in the runtime in terms of $\Delta$, $k$ and $N$, this
gets us that $T(k)=N^{O(k\Delta)}$. ∎

Algorithm 2 ApproxZ

1:Input

2: $G=(V,E)$Bounded degree Graph with at least 1 vertex

3: $k$Computation Depth

4: $\alpha$Value in $[0,0.5)$

5: $N$Positive Integer

6:Output

7: $\tilde{Z}(G)$Estimate of $Z(G)$, the number of restricted relaxed
independent sets in $G$

8:Let $z\\_inv=1$

9:Let $\beta=()$

10:for $v\in V$ do

11: $z\\_inv\leftarrow
z\\_inv*\operatorname{ApproxProb}(G,k,v,\alpha,0,N,\beta)$

12: $\beta\leftarrow(\beta,v\leftarrow 0)$

13:end for

14:Return $1/z\\_inv$

###  5.2 Counting Algorithm

We now introduce Algorithm 2 ApproxZ, which will approximately compute $Z(G)$,
the number of restricted relaxed independent sets in the graph $G$. This
algorithm directly computes the telescoping definition of $Z(G)$ using the
approximated marginal probabilities produced by Algorithm 1. We will show the
following main result.

######  Theorem 17.

For any graph $G$ of maximum degree $\Delta$ with $m$ vertices, Algorithm 2
will produce an estimate $\hat{Z}(G)$ satisfying

$1-O(1/m)\leq\frac{\hat{Z}(G)}{Z(G)}\leq O(1/m),$

for any $N$ and any $\alpha>\alpha_{\Delta}$ for some $k$ which is $O(\log
mN)$. Further, the algorithm will run in $N^{O(\Delta\log Nm)}$ time.

###### Proof.

Since $\alpha>\alpha_{\Delta}$, we have that $\|\nabla f_{n}\|_{1}\leq c<1$
with respect to every vertex $v$ in ever subgraph of $G$. Observe that
equations 4 and 5 together imply that $y(G,v\leftarrow
0,\beta)\geq\frac{1}{(1-\alpha)N+1}$. Thus, letting
$k=\log_{c}\left(\frac{1}{((1-\alpha)\alpha N+1)m^{2}}\right)$ in the
execution of Algorithm 2, Lemma 16 says the estimates $y(G,v_{k}\leftarrow
0,\beta_{k-1})$ of $x(G,v_{k}\leftarrow 0,\beta_{k-1})$ will satisfy

$|x(G,v_{k}\leftarrow 0,\beta_{k-1})-y(G,v_{k}\leftarrow
0,\beta_{k-1})|\leq\frac{1}{((1-\alpha)N+1)m^{2}}\leq\frac{y(G,v_{k}\leftarrow
0,\beta_{k-1})}{m^{2}}.$

Dividing both sides of the equation by $y(G,v_{k}\leftarrow 0,\beta_{k-1})$
results in

$|\frac{x(G,v_{k}\leftarrow 0,\beta_{k-1})}{y(G,v_{k}\leftarrow
0,\beta_{k-1})}-1|\leq\frac{1}{m^{2}}.$

As discussed in Section 2, this bound is sufficient to show that the estimate
$\hat{Z}(G)$ satisfies

$1-O(1/m)\leq\frac{\hat{Z}(G)}{Z(G)}\leq O(1/m).$

We finish by noting that since $c<1$, $k$ is $O(\log mN)$ for constant
$\alpha$. The bound on the running time follows directly from the bound in
Lemma 16. ∎

##  6 From Counting to Volumes

Now that we have an algorithm to count restricted relaxed independent sets, we
move to showing how one can approximate the volume of $\mathcal{P}_{\rm
IS}(G,\alpha)$ using this discrete approximation.

Fix an arbitrary graph $G=(V,E)$ with $V=\\{v_{1},\ldots v_{m}\\}$, where each
vertex has degree at most $\Delta$. We define a set of graphs
$G_{n}=(\\{v_{1},\ldots v_{n}\\},E_{n})$ where $E_{n}=\\{(v_{i},v_{j})\in
E|i,j\leq n\\}$, so that $G_{m}=G$. Additionally, fix
$\alpha\geq\alpha_{\Delta}$ and $N$. Since we will be inducting over the size
of the graph, we will redefine $\beta$ to be a set of constraints of the form
$x_{i}\leq c$, and have $\beta_{i}$ denote the tightest constraint on $x_{i}$.
In particular, meaning any x satisfying every constraint in $\beta$ satisfies
$x_{i}\leq\beta_{i}$. Similarly, we will redefine $v_{i}\leftarrow c$ to be
the set of constraints $\\{x_{j}\leq N-c|(v_{i},v_{j})\in E\\}$. We assume
that $\alpha N\leq\beta_{i}\leq(1-\alpha)N$. Under this setup, we define the
following family of polytopes,

$\mathcal{Q}(G_{n},\alpha,\beta)=\\{\textbf{x}\in\mathbb{R}^{n}:0\leq
x_{i}\leq\beta_{i}\ \forall i\in[1,n],x_{i}+x_{j}\leq N\
\forall(v_{i},v_{j})\in E_{n}\\}.$

We will show that for any such polytope, we can approximate its volume by
counting the number of restricted relaxed independent sets in $G$. To do this,
we define the following two sets,

$\displaystyle\mathcal{U}(G_{n},\alpha,\beta)$
$\displaystyle=\\{\textbf{x}\in\mathbb{Z}^{n}:0\leq x_{i}\leq\beta_{i}\
\forall i\in[1,n],x_{i}+x_{j}\leq N\ \forall(v_{i},v_{j})\in E_{n}\\},$
$\displaystyle\mathcal{L}(G,\alpha,\beta)$
$\displaystyle=\\{\textbf{x}\in\mathbb{Z}^{n}:0\leq x_{i}\leq\beta_{i}-1\
\forall i\in[1,n],x_{i}+x_{j}\leq N-2\ \forall(v_{i},v_{j})\in E_{n}\\}.$

Notice that
$\frac{\mathcal{Q}(G,\alpha,\beta)}{N^{m}}\subseteq\mathcal{P}_{\rm
IS}(G,\alpha)$, and when $\beta$ is such that $\beta_{i}=(1-\alpha)N,\forall
i$, $|\mathcal{U}(G,\alpha,\beta)|=Z(G)$ and
$\frac{\mathcal{Q}(G,\alpha,\beta)}{N^{m}}=\mathcal{P}_{\rm IS}(G,\alpha)$.

######  Lemma 18 (Volume Bound).

For any graph $G$ and any $n,\beta,\alpha,N$,

$|\mathcal{L}(G,\alpha,\beta)|\leq\operatorname{Vol}(\mathcal{Q}(G_{n},\alpha,\beta))\leq|\mathcal{U}(G_{n},\alpha,\beta)|.$

###### Proof.

We first show the lower bound. Take any vector
$\textbf{x}\in\mathcal{L}(G,\alpha,\beta)$. It follows immediately from
construction that $\textbf{x}\in\mathcal{Q}(G_{n},\alpha,\beta)$. Further, For
any vector $\textbf{y}\in[0,1)^{n}$, we have that $x_{i}+y_{i}\leq\beta_{i}$
and $(x_{i}+y_{i})+(x_{j}+y_{j})\leq x_{i}+x_{j}+2\leq N$ for every $(i,j)\in
E_{n}$. Thus, $\textbf{x}+\textbf{y}\in\mathcal{Q}(G_{n},\alpha,\beta)$ for
every such y. Since we can associate a distinct unit cube within
$\mathcal{Q}(G_{n},\alpha,\beta)$ to each point
$\textbf{x}\in\mathcal{L}(G,\alpha,\beta)$, we get that
$|\mathcal{L}(G,\alpha,\beta)|\leq\operatorname{Vol}(\mathcal{Q}(G_{n},\alpha,\beta))$
as desired.

Next we show the upper bound. Consider any vector
$\textbf{y}\in\mathcal{Q}(G_{n},\alpha,\beta)$, and let
$\lfloor\textbf{y}\rfloor$ be the vector y with each entry truncated to the
highest integer value from below. We clearly have
$\lfloor\textbf{y}\rfloor\in\mathcal{U}(G_{n},\alpha,\beta)$. Assigning a cube
of side length one to each $\textbf{x}\in\mathcal{U}(G_{n},\alpha,\beta)$, we
obtain a space which contains $\mathcal{Q}(G_{n},\alpha,\beta)$. Thus,
$\operatorname{Vol}(\mathcal{Q}(G_{n},\alpha,\beta))\leq|\mathcal{U}(G_{n},\alpha,\beta)|$.
∎

Now, we move on to the main theorem of this section.

######  Theorem 19 (Volume Approximation).

For any graph $G$ and any of $n,\beta,\alpha,N$,

$\left(1-\frac{n}{\alpha
N}\right)|\mathcal{U}(G_{n},\alpha,\beta)|\leq\operatorname{Vol}(\mathcal{Q}(G_{n},\alpha,\beta))\leq|\mathcal{U}(G_{n},\alpha,\beta)|.$

###### Proof.

Let $\textbf{x}\in\mathcal{U}(G_{n},\alpha,\beta)$ be picked uniformly at
random. Further, let
$\mu_{\beta}^{n}=\Pr(\textbf{x}\not\in\mathcal{L}(G,\alpha,\beta))=\frac{|\mathcal{U}(G_{n},\alpha,\beta)|-|\mathcal{L}(G,\alpha,\beta)|}{|\mathcal{U}(G_{n},\alpha,\beta)|}$.
We will show $\mu_{\beta}^{n}\leq\frac{n}{\alpha N}$ by induction on $n$. This
will directly imply the result by Lemma 18 since
$|\mathcal{L}(G_{n},\alpha,\beta)|=(1-\mu_{\beta}^{n})|\mathcal{U}(G_{n},\alpha,\beta)|$.
In the base case, if $n=1$, then
$\mu_{\beta}^{1}=\Pr(x_{1}\leftarrow\beta_{1})=\frac{1}{\beta_{1}+1}\leq\frac{1}{\alpha
N}$, since $x_{1}$ is uniformly distributed over $[0,\beta_{1}]$ and
$\beta_{1}\geq\alpha N$.

We now proceed by induction. First, notice that for any
$\textbf{x}\in\mathcal{U}(G_{n},\alpha,\beta)$, replacing the $n$th entry of x
with any smaller value will produce a new
$\textbf{x}^{\prime}\in\mathcal{U}(G_{n},\alpha,\beta)$. In particular, this
means for any $0\leq j\leq i$, it must be that $\Pr(x_{n}\leftarrow
i)\leq\Pr(x_{n}\leftarrow j)$. Thus,

$\Pr(x_{n}\leftarrow i)\leq\frac{\Pr(x_{n}\leftarrow
i)}{\sum_{j=0}^{i}\Pr(x_{n}\leftarrow j)}\leq\frac{\Pr(x_{n}\leftarrow
i)}{(i+1)\Pr(x_{n}\leftarrow i)}=\frac{1}{i+1},$

and since $\beta_{n}\geq\alpha N$, we get that
$\Pr(x_{n}\leftarrow\beta_{i})\leq\frac{1}{\alpha N}$.

Next, consider any $\textbf{x}\in\mathcal{U}(G_{n},\alpha,\beta)$ with
$x_{n}=k$ where $\textbf{x}\not\in\mathcal{L}(G,\alpha,\beta)$. It must be
that either $x_{n}=\beta_{n}$ or $(x_{1},\ldots
x_{n-1})\not\in\mathcal{L}(G_{n-1},\alpha,(\beta,v_{n}\leftarrow k))$. Notice
that $k\leq(1-\alpha)N$, since $\beta_{n}\leq(1-\alpha)N$ by assumption.
Therefore, we can use the inductive hypothesis to see

$\displaystyle\mu_{\beta}^{n}$
$\displaystyle=\Pr(x_{n}\leftarrow\beta_{n})+\sum\limits_{i=0}^{\beta_{i}-1}\Pr(x_{n}\leftarrow
i)\mu^{n-1}_{(\beta,x_{n}\leftarrow i)}$ $\displaystyle\leq\frac{1}{\alpha
N}+\sum\limits_{i=0}^{\beta_{i}-1}\Pr(x_{n}\leftarrow i)\frac{n-1}{\alpha N}$
$\displaystyle\leq\frac{n}{\alpha N}.$

∎

With this analysis, we are ready to complete the proof of our main result,
Theorem 1.

###### Proof of Theorem 1.

We will actually prove an asymptotically stronger result, namely that there is
an algorithm running in $m^{O(\log m)}$ time which produces a value
$\tilde{V}$ satisfying

$1-O(1/m)\leq\frac{\tilde{V}}{\operatorname{Vol}(\mathcal{P}_{\rm
IS}(G,\alpha))}\leq 1+O(1/m)$

when $G$ is an $m$ node graph with a maximum degree of $\Delta$ and
$\alpha>\alpha_{\Delta}$. The proof which follows can be modified to a proof
of the main theorem by setting $N$ to be $O(m/\epsilon)$ and modifying Theorem
17 to have $k$ be $O(\log m/\epsilon)$.

We start by setting $N=\frac{m^{2}}{\alpha}$. Let $\beta$ be such that
$\beta_{i}=(1-\alpha)N$ for every $i$. We have that
$\mathcal{P}_{\text{IS}}(G,\alpha)=\frac{\mathcal{Q}(G,\alpha,\beta)}{N^{m}}$.
By Theorem 19, we have

$\left(1-\frac{m}{\alpha
N}\right)|\mathcal{U}(G,\alpha,\beta)|=\left(1-\frac{1}{m}\right)|\mathcal{U}(G,\alpha,\beta)|\leq\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))\leq|\mathcal{U}(G,\alpha,\beta)|,$

as a result

$|\mathcal{U}(G,\alpha,\beta)|-\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))|=|\mathcal{U}(G,\alpha,\beta)|-\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))\leq\frac{1}{m}|\mathcal{U}(G,\alpha,\beta)|\leq\frac{2}{m}\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta)),$

where the last inequality follows from $1-\frac{1}{m}\geq\frac{1}{2}$ (unless
the graph is trivial) implying that
$2\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))\geq|\mathcal{U}(G,\alpha,\beta)|$.
Additionally, we have that $|\mathcal{U}(G,\alpha,\beta)|=Z(G)$ by
construction. Theorem 17 implies the existence of a deterministic algorithm to
produce an estimate $\tilde{Z}(G)$ satisfying
$|\tilde{Z}(G)-|\mathcal{U}(G,\alpha,\beta)||\leq
c|\mathcal{U}(G,\alpha,\beta)|/m$ for some universal constant $c$. Thus, we
get

$\displaystyle|\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))-\tilde{Z}(G,\alpha)|$
$\displaystyle\leq|\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))-|\mathcal{U}(G,\alpha,\beta)||+||\mathcal{U}(G,\alpha,\beta)|-\tilde{Z}(G,\alpha)|$
$\displaystyle\leq\frac{2}{m}\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))+\frac{c}{m}|\mathcal{U}(G,\alpha,\beta)|$
$\displaystyle\leq\frac{2}{m}\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))+\frac{2c}{m}\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))$
$\displaystyle=\frac{2c+2}{m}\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta)),$

where the last inequality again holds because
$2\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))\geq|\mathcal{U}(G,\alpha,\beta)|$.
Therefore, we can take $\tilde{V}=\frac{\tilde{Z}(G,\alpha)}{N^{m}}$ to be our
estimate of the volume of $\mathcal{P}_{\text{IS}}$ to see

$|\operatorname{Vol}(\mathcal{P}_{\text{IS}})-\frac{\tilde{Z}(G,\alpha)}{N^{m}}|=\frac{1}{N^{m}}|\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))-\tilde{Z}(G,\alpha)|\leq\frac{2c+2}{mN^{m}}\operatorname{Vol}(\mathcal{Q}(G,\alpha,\beta))=\frac{2c+2}{m}\operatorname{Vol}(\mathcal{P}_{\text{IS}}).$

Additionally, substituting in the value of $N$, the algorithm from Theorem 17
will run in $m^{O(\Delta\log m)}$ time.

∎

##  7 Barriers to the $\alpha=0$ Case

In this section, we discuss some challenges we encounter when designing an
algorithm to compute the volume of the unrestricted ($\alpha=0$) independent
set polytope. While the gradient bound given in Section 4 is loose and some
adjustment to the argument may admit an asymptotic improvement on our values
of $\alpha_{\Delta}$, it clearly will not generalize to $\alpha=0$. In fact,
we have been able to show computationally that the values of $|\nabla
f_{n}|_{1}$, with $f_{n}$ defined as in 3 exceeds 1 in bounded degree graphs
when $\alpha=0$. We set $N=64$ and take a 4-regular tree of depth 50, and
assigned each leaf vertex 0 with probability 1. We were than able to
repeatedly apply equation 3 to produce a probability distribution for the
assignment of the vertices at each level of the tree. We know that correlation
decay holds on trees [11], so the probability distributions quickly converges
to a fixed point distribution. At depth 50, the probability of a vertex being
assigned a value $n$ had converged within 5 significant decimal places.

We evaluated $|\nabla f_{n}(\textbf{x})|_{1}$ for each $n$ with this
probability distribution x. We found that for $n\leq 13$, $|\nabla
f_{n}(\textbf{x})|_{1}>1$. When we modified $N$, we found that roughly the
same proportion of values $n$ satisfied $|\nabla f_{n}(\textbf{x})|_{1}>1$.
Increasing the degree of the tree increased the number of $n$ where $|\nabla
f_{n}(\textbf{x})|_{1}>1$.

Since we initialized each leaf node with the same value, every vertex at a
specified depth in our tree will have the same probability distribution over
$[0,N]$. Thus, we can modify equation 3 to be only a function of $x_{0},\ldots
x_{N}$, where $x_{i}$ is the probability a vertex of depth one below our
current vertex is assigned $i$. This allows us to construct the $N+1\times
N+1$ matrix $M$, where $M_{ij}=\frac{\partial f_{i}(\textbf{x})}{\partial
x_{j}}$. In all of the cases above, we found that this matrix $M$ had a
largest singular value greater than 1, and thus had an operator norm exceeding
1. This seems to suggest that methods of showing correlation decay which
relies on showing a universal single step contraction, such as one similar to
([6]) does not succeed. It is possible that methods based on multi-step
contraction or based on other single step but non-spectral type of contraction
do succeed. We leave it as a very interesting question for further research.

## References

  * Anari et al., [2021] Anari, Nima, Liu, Kuikui, & Gharan, Shayan Oveis. 2021.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  SIAM Journal on Computing, 0(0), FOCS20–1.
  * Bandyopadhyay & Gamarnik, [2006] Bandyopadhyay, A., & Gamarnik, D. 2006.  Counting without sampling. New algorithms for enumeration problems using statistical physics.  In: Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms (SODA).
  * Bandyopadhyay & Gamarnik, [2008] Bandyopadhyay, A., & Gamarnik, D. 2008.  Counting without sampling. Asymptotics of the log-partition function for certain statistical physics models.  Random Structures and Algorithms, 33(4), 452–479.
  * Bárány & Füredy, [1987] Bárány, I., & Füredy, Z. 1987.  Computing the volume is difficult.  Discrete Comput. Geom., 2(4), 319–326.
  * Barvinok, [2017] Barvinok, Alexander. 2017.  Combinatorics and Complexity of Partition Functions.  Algorithms and Combinatorics, 30.
  * Chen et al., [2023] Chen, Zongchen, Liu, Kuikui, Mani, Nitya, & Moitra, Ankur. 2023.  Strong spatial mixing for colorings on trees and its algorithmic applications.  arXiv preprint arXiv:2304.01954.
  * Dyer & an R. Kannan, [1991] Dyer, M. E., & an R. Kannan, A. Frieze. 1991.  A random polynomial time algorithm for approximating the volume of convex bodies.  Journal of the Association for Computing Machinery, 38, 1–17.
  * Dyer & Frieze, [1988] Dyer, Martin E., & Frieze, Alan M. 1988.  On the complexity of computing the volume of a polyhedron.  SIAM Journal on Computing, 17(5), 967–974.
  * Gamarnik & Katz, [2012] Gamarnik, D., & Katz, D. 2012.  Correlation decay and deterministic FPTAS for counting list-colorings of a graph.  Journal of Discrete Algorithms, 12, 29–47.
  * Gamarnik, [2023] Gamarnik, David. 2023.  Correlation decay and the absence of zeros property of partition functions.  Random Structures & Algorithms, 62, 155–180.
  * Gamarnik & Ramanan, [2019] Gamarnik, David, & Ramanan, Kavita. 2019.  Uniqueness of Gibbs measures for continuous hardcore models.  The Annals of Probability, 47(4).
  * Patel & Regts, [2017] Patel, Viresh, & Regts, Guus. 2017.  Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials.  SIAM Journal on Computing, 46(6), 1893–1919.
  * Regts, [2023] Regts, Guus. 2023.  Absence of zeros implies strong spatial mixing.  Probability Theory and Related Fields, 1–21.
  * Sly, [2010] Sly, Allan. 2010.  Computational transition at the uniqueness threshold.  Pages 287–296 of: Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on.  IEEE.
  * Trevisan, [2006] Trevisan, Luca. 2006.  Pseudorandomness and combinatorial constructions.  Pages 1111–1136 of: Proceedings oh the International Congress of Mathematicians: Madrid, August 22-30, 2006: invited lectures.
  * Weitz, [2006] Weitz, D. 2006.  Counting independent sets up to the tree threshold.  In: Proc. 38th Ann. Symposium on the Theory of Computing.