$\varepsilon/3$-close in total variation distance to
$\mu_{P,\beta}(\cdot\mid\mathcal{Y})$ with the following rejection sampling
algorithm:

    1. 2.1

Generate $\sigma_{P}\in\\{+1,-1\\}^{P}$ from the product distribution
$Q_{P}^{\mathcal{Y}}$;

    2. 2.2

Compute the approximation $\hat{Z}(\sigma_{P})$ for
$Z_{\widehat{F},\beta}(\sigma_{P},\mathcal{Y})$ such that

$\left(1-\frac{\varepsilon}{10}\right)Z_{\widehat{F},\beta}(\sigma_{P},\mathcal{Y})\leq\hat{Z}(\sigma_{P})\leq\left(1+\frac{\varepsilon}{10}\right)Z_{\widehat{F},\beta}(\sigma_{P},\mathcal{Y});$

this can be done in time $\mathrm{poly}(|V_{\widehat{F}}|,1/\varepsilon)$ with
success probability at least $1-\varepsilon/3$ by Lemma 5.4.

    3. 2.3

Accept $\sigma_{P}$ with probability:

$r(\sigma_{P})=\frac{1}{10}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{\hat{Z}(\sigma_{P})}{\hat{Z}(\sigma^{+})}.$

    4. 2.4

Repeat until accept or exceed $T=c\log(1/\varepsilon)$ rounds, for a suitable
constant $c>0$, in which case we let $\sigma_{P}=\sigma^{+}$.

  3. 3.

Sample the configuration of each gadget $G_{v}$ conditional on the port
configuration $\sigma_{P_{v}}$ on $P_{v}$ from a distribution
$\frac{\varepsilon}{3|V_{F}|}$-close to
$\mu_{G_{v},\beta}(\cdot\mid\sigma_{P_{v}})$ with the algorithm from Lemma 5.4

  4. 4.

Output the resulting configuration $\sigma$.

For the analysis of this algorithm, let us focus first on the rejection
sampling process in Step 2. First, note that the process is well-defined
since:

$r(\sigma_{P})=\frac{1}{10}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{\hat{Z}(\sigma_{P})}{\hat{Z}(\sigma^{+})}\leq\frac{1}{5}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{Z_{\widehat{F},\beta}(\sigma_{P},\mathcal{Y})}{Z_{\widehat{F},\beta}(\sigma^{+},\mathcal{Y})}=\frac{1}{5}\cdot\frac{\mu_{P,\beta}(\sigma_{P}\mid\mathcal{Y})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{\mu_{P,\beta}(\sigma^{+}\mid\mathcal{Y})}\leq
1,$

where the last inequality follows from Lemma 5.6. Second, each iteration of
the the rejection sampling algorithm can be implemented in polynomial time; in
particular, we can compute compute $r(\sigma_{P})$ using the FPRAS from Lemma
5.4 to obtain $\hat{Z}(\sigma_{P})$ and $\hat{Z}(\sigma^{+})$. Finally, we
claim that the output of this algorithm is at least $\varepsilon/3$-close to
$\mu_{P,\beta}(\cdot\mid\mathcal{Y})$ in total variation distance. To see
this, note that for each $\sigma_{P}\in\\{+1,-1\\}^{P}$, the probability that
process outputs $\sigma_{P}$ in one round is:

$Q_{P}^{\mathcal{Y}}(\sigma_{P})r(\sigma_{P})=\frac{1}{10}\cdot
Q_{P}^{\mathcal{Y}}(\sigma^{+})\cdot\frac{\hat{Z}(\sigma_{P})}{\hat{Z}(\sigma^{+})}\propto\hat{Z}(\sigma_{P}).$

Therefore, conditioned on the algorithm accepting on the first
$T=c\log(1/\varepsilon)$ rounds, the probability that $\sigma_{P}$ is the
output is

$\frac{\hat{Z}(\sigma_{P})}{\sum_{\sigma^{\prime}}\hat{Z}({\sigma^{\prime}})}\leq\left(1+\frac{\varepsilon}{5}\right)\frac{Z_{\widehat{F},\beta}(\sigma_{P},\mathcal{Y})}{\sum_{\sigma^{\prime}}Z_{\widehat{F},\beta}(\sigma^{\prime},\mathcal{Y})}=\left(1+\frac{\varepsilon}{5}\right)\mu_{P,\beta}(\sigma_{P}\mid\mathcal{Y}),$

and similarly for the lower bound. Moreover, since by Lemma 5.6

$\displaystyle r(\sigma_{P})$
$\displaystyle=\frac{1}{10}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{\hat{Z}(\sigma_{P})}{\hat{Z}(\sigma^{+})}\geq\frac{1}{20}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{Z_{\widehat{F},\beta}(\sigma_{P},\mathcal{Y})}{Z_{\widehat{F},\beta}(\sigma^{+},\mathcal{Y})}$
$\displaystyle=\frac{1}{20}\cdot\frac{\mu_{P,\beta}(\sigma_{P}\mid\mathcal{Y})}{Q_{P}^{\mathcal{Y}}(\sigma_{P})}\cdot\frac{Q_{P}^{\mathcal{Y}}(\sigma^{+})}{\mu_{P,\beta}(\sigma^{+}\mid\mathcal{Y})}\geq\frac{1}{100},$

the probability that the algorithm accepts in the first
$T=c\log(1/\varepsilon)$ rounds is at least

$1-\left(1-\frac{1}{100}\right)^{c\log(1/\varepsilon)}\geq
1-\frac{\varepsilon}{10},$

for a suitable constant $c>0$.

Now, note that by Lemma 5.7 and union bound, the phase vector of $\sigma$
agrees with $\mathcal{Y}$ with probability at least
$1-|T|e^{-\Omega(n^{3\theta/4})}$; hence, the output distribution of the
algorithm satisfies:

$d_{\mathrm{TV}}\left(\mu_{\textsc{alg}},\mu_{\widehat{F},\beta}(\cdot\mid\mathcal{Y})\right)\leq\frac{\varepsilon}{3}+\frac{\varepsilon}{3}+|V_{F}|\cdot\frac{\varepsilon}{3|V_{F}|}+|T|e^{-\Omega(n^{3\theta/4})}+{2^{-n^{\theta/4}}}\leq\varepsilon+\log(1/\varepsilon)e^{-\Omega(n^{\theta/4})},$

as claimed. ∎

###  5.4 Sampling conditional on the phase vector: proof of auxiliary facts

We provide in this section the proofs of Lemmas 5.3, 5.4, 5.6 and 5.7.

###### Proof of Lemma 5.3.

We have

$d_{\mathrm{TV}}\left(\mu_{\widehat{F},\beta}(\cdot\mid
Y(\sigma)\in\Omega_{0}),\mu_{\widehat{F},\beta}(\cdot\mid
Y(\sigma)\in\Omega_{st})\right)=\sum_{\sigma:Y(\sigma)\in\Omega_{0}\setminus\Omega_{st}}\mu_{\widehat{F},\beta}(\sigma\mid
Y(\sigma)\in\Omega_{0}).$

This is the probability of obtaining a phase vector in
$\Omega_{0}\setminus\Omega_{st}$ under $\mu_{\widehat{F},\beta}(\cdot\mid
Y(\sigma)\in\Omega_{0}$. Observe that among all the cuts of $F$ corresponding
to phase vectors in $\Omega_{0}$, the largest ones are those corresponding to
the phase vectors in $\Omega_{st}$. Hence, following the argument in the proof
of Lemma 5.1, we get from the results in [Sly10, GŠV16, CGG+16] that this
probability is at least $1-1/2^{n^{\theta/4}}$ as desired. ∎

###### Proof of Lemma 5.6.

Let $\sigma\in\\{+1,-1\\}^{P}$. Let
$Z_{\widehat{F},\beta}(\sigma,\mathcal{Y})$ be the sum of the weights of all
the configurations of $\widehat{F}$ with phase vector $\mathcal{Y}$ that agree
with $\sigma$ in $P$ and, similarly, define
$Z_{\widehat{F},\beta}(\mathcal{Y})$ as the sum of the weights of all
configurations with phase vector $\mathcal{Y}$, so that

$\displaystyle\mu_{P,\beta}(\sigma\mid\mathcal{Y})=\frac{Z_{\widehat{F},\beta}(\sigma,\mathcal{Y})}{Z_{\widehat{F},\beta}(\mathcal{Y})}=\frac{1}{Z_{\widehat{F},\beta}(\mathcal{Y})}\cdot\prod_{v\in
V_{F}}Z_{G_{v},\beta}(\sigma_{P_{v}},\mathcal{Y}_{v})\cdot\prod_{\\{u,v\\}\in
E(P)}e^{\beta\sigma_{u}\sigma_{v}}.$

By Lemma 5.5, we have

$\displaystyle\mu_{P,\beta}(\sigma\mid\mathcal{Y})$
$\displaystyle\leq\frac{(1+n^{-2\theta})^{|V_{F}|}}{Z_{\widehat{F},\beta}(\mathcal{Y})}\prod_{v\in
V_{F}}Z_{G_{v},\beta}(\mathcal{Y}_{v})Q_{v}^{\mathcal{Y}_{v}}(\sigma_{P_{v}})\prod_{\\{u,v\\}\in
E(P)}e^{\beta\sigma_{u}\sigma_{v}}$
$\displaystyle=\frac{(1+n^{-2\theta})^{|V_{F}|}}{Z_{\widehat{F},\beta}}\cdot
w_{P}^{\mathcal{Y}}(\sigma)\cdot\prod_{v\in
V_{F}}Z_{G_{v},\beta}(\mathcal{Y}_{v}).$

Then,

$\frac{\mu_{P,\beta}(\sigma\mid\mathcal{Y})}{Q_{P}^{\mathcal{Y}}(\sigma)}\leq(1+n^{-2\theta})^{|V_{F}|}\cdot\frac{Z_{P}^{\mathcal{Y}}}{Z_{\widehat{F},\beta}}\cdot\prod_{v\in
V_{F}}Z_{G_{v},\beta}(\mathcal{Y}_{v}).$

Now,

$\displaystyle Z_{P}^{\mathcal{Y}}\cdot\prod_{v\in
V_{F}}Z_{G_{v},\beta}(\mathcal{Y}_{v})$
$\displaystyle=\sum_{\sigma\in\\{+1,-1\\}^{P}}\prod_{\\{u,v\\}\in
E(P)}e^{\beta\sigma_{u}\sigma_{v}}\cdot\prod_{v\in
V_{F}}Q_{v}^{\mathcal{Y}_{v}}(\sigma_{P_{v}})Z_{G_{v},\beta}(\mathcal{Y}_{v}).$

From Eq. 15, we have

$\frac{1}{1+n^{-2\theta}}\mu_{P_{v},\beta}(\sigma_{P_{v}}\mid\mathcal{Y}_{v})\leq
Q_{v}^{\mathcal{Y}_{v}}(\sigma_{P_{v}})\leq\frac{1}{1-n^{-2\theta}}\mu_{P_{v},\beta}(\sigma_{P_{v}}\mid\mathcal{Y}_{v}),$

and so

$\displaystyle Z_{P}^{\mathcal{Y}}\cdot\prod_{v\in
V_{F}}Z_{G_{v},\beta}(\mathcal{Y}_{v})$
$\displaystyle\leq\frac{1}{(1-n^{-2\theta})^{|V_{F}|}}\sum_{\sigma\in\\{+1,-1\\}^{P}}\prod_{\\{u,v\\}\in
E(P)}e^{\beta\sigma_{u}\sigma_{v}}\cdot\prod_{v\in
V_{F}}\mu_{P_{v},\beta}(\sigma_{P_{v}}\mid\mathcal{Y}_{v})Z_{G_{v},\beta}(\mathcal{Y}_{v})$
$\displaystyle=\frac{1}{(1-n^{-2\theta})^{|V_{F}|}}Z_{\widehat{F},\beta}.$

Thus, we have obtained the upper bound

$\frac{\mu_{P,\beta}(\sigma\mid\mathcal{Y})}{Q_{P}^{\mathcal{Y}}(\sigma)}\leq\left(\frac{1+n^{-2\theta}}{1-n^{-2\theta}}\right)^{|V_{F}|},$

and in we can deduce analogously that

$\frac{\mu_{P,\beta}(\sigma\mid\mathcal{Y})}{Q_{P}^{\mathcal{Y}}(\sigma)}\geq\left(\frac{1-n^{-2\theta}}{1+n^{-2\theta}}\right)^{|V_{F}|}.$

Recall that $|V_{F}|=n^{\theta/12}+2$, so that

$1-o(1)\leq\frac{\mu_{P,\beta}(\sigma\mid\mathcal{Y})}{Q_{P}^{\mathcal{Y}}(\sigma)}\leq
1+o(1)$

and the result follows. ∎

###### Proof of Lemma 5.7.

Consider a gadget $G_{v}$ of $\widehat{F}$ such that $\mathcal{Y}_{v}=+1$. Let
$u\in P_{v}^{+}$. We claim that since $p^{+}>1/2$, then
$Q_{P}^{\mathcal{Y}}(\sigma_{u}=-1)>1/2$. To see this, let $w$ be the neighbor
of $u$ in $P$ and suppose that the phase of the gadget containing $w$ is $+1$.
Then,

$\frac{Q_{P}^{\mathcal{Y}}(\sigma_{u}=-1)}{Q_{P}^{\mathcal{Y}}(\sigma_{u}=+1)}=\frac{(p^{+})^{2}e^{\beta}+p^{+}(1-p^{+})e^{-\beta}}{(1-p^{+})^{2}e^{\beta}+p^{+}(1-p^{+})e^{-\beta}}>1,$

which implies that $Q_{P}^{\mathcal{Y}}(\sigma_{u}=-1)>1/2$. An analogous
calculation shows that the same holds when the gadget containing $w$ is in the
$-1$ phase. With the same reasoning, we can similarly deduce that when $u\in
P_{v}^{-}$, then $Q_{P}^{\mathcal{Y}}(\sigma_{u}=+1)>1/2$. This implies by a
Chernoff bound that if $\sigma_{P}\sim Q_{P}^{\mathcal{Y}}$ and
$\mathcal{Y}_{v}=+1$, then there exists a constant $\delta>0$ such that:

$|\sigma^{-}_{P_{v}}(-1)\cap P_{v}^{+}|-|\sigma_{P_{v}}^{-}(-1)\cap
P_{-}^{v}|\geq\delta|P_{v}|,$

and

$|\sigma_{P_{v}}^{-}(+1)\cap P_{-}^{v}|-|\sigma_{P_{v}}^{-}(+1)\cap
P_{+}^{v}|\geq\delta|P_{v}|,$

with probability at least $1-\exp(-\Omega(|P_{v}|))$.

Now,

$\displaystyle\frac{\mu_{G_{v},\beta}(\mathcal{Y}_{v}=+1\mid\sigma_{P_{v}})}{\mu_{G_{v},\beta}(\mathcal{Y}_{v}=-1\mid\sigma_{P_{v}})}$
$\displaystyle=\frac{\mu_{G_{v},\beta}(\sigma_{P_{v}}\mid\mathcal{Y}_{v}=+1)}{\mu_{G_{v},\beta}(\sigma_{P_{v}}\mid\mathcal{Y}_{v}=-1)}\cdot\frac{\mu_{G_{v},\beta}(\mathcal{Y}_{v}=+1)}{\mu_{G_{v},\beta}(\mathcal{Y}_{v}=-1)}$
$\displaystyle\geq\left(1-\frac{c}{n^{2\theta}}\right)\cdot\frac{Q_{v}^{+}(\sigma_{P_{v}})}{Q_{v}^{-}(\sigma_{P_{v}})}\cdot\frac{\mu_{\widehat{F},\beta}(\mathcal{Y}_{v}=+1)}{\mu_{\widehat{F},\beta}(\mathcal{Y}_{v}=-1)},$

by Lemma 5.5. Lemma 5.5 also implies that
$\frac{\mu_{G_{v},\beta}(\mathcal{Y}_{v}=+1)}{\mu_{G_{v},\beta}(\mathcal{Y}_{v}=-1)}\geq\frac{1}{n}$.
Moreover, from the definition of $Q_{v}^{+}$ and $Q_{v}^{-}$ we have

$\displaystyle\frac{Q_{v}^{+}(\sigma_{P_{v}})}{Q_{v}^{-}(\sigma_{P_{v}})}$
$\displaystyle=\frac{(p^{+})^{|\sigma_{P_{v}}^{-}(-1)\cap
P_{+}^{v}|}(1-p^{+})^{|\sigma_{P_{v}}^{-}(+1)\cap
P_{+}^{v}|}(p^{-})^{|\sigma_{P_{v}}^{-}(-1)\cap
P_{-}^{v}|}(1-p^{-})^{|\sigma_{P_{v}}^{-}(+1)\cap
P_{-}^{v}|}}{(p^{-})^{|\sigma_{P_{v}}^{-}(-1)\cap
P_{+}^{v}|}(1-p^{-})^{|\sigma_{P_{v}}^{-}(+1)\cap
P_{+}^{v}|}(p^{+})^{|\sigma_{P_{v}}^{-}(-1)\cap
P_{-}^{v}|}(1-p^{+})^{|\sigma_{P_{v}}^{-}(+1)\cap P_{-}^{v}|}}$
$\displaystyle=\left(\frac{p^{+}}{p^{-}}\right)^{|\sigma_{P_{v}}^{-}(-1)\cap
P_{+}^{v}|-|\sigma_{P_{v}}^{-}(-1)\cap
P_{-}^{v}|}\left(\frac{1-p^{-}}{1-p^{+}}\right)^{|\sigma_{P_{v}}^{-}(+1)\cap
P_{-}^{v}|-|\sigma_{P_{v}}^{-}(+1)\cap P_{+}^{v}|}$ $\displaystyle\geq
a^{\delta|P_{v}|},$

for a suitable constant $a>1$ since $p^{+}>1/2$ and $p^{-}<1/2$. This implies
that for a suitable constant $c_{0}>0$, we have

$\mu_{G_{v},\beta}(\mathcal{Y}_{v}=+1\mid\sigma_{P_{v}})\geq
1-\frac{c_{0}n}{a^{\delta|P_{v}|}}\geq 1-\frac{c_{0}n}{a^{\delta
n^{3\theta/4}}},$

since $|P_{v}|\geq n^{3\theta/4}$. Finally, we note that

$\mu_{\widehat{F},\beta}(\mathcal{Y}\mid\sigma_{P})=\prod_{v\in
V_{F}}\mu_{G_{v},\beta}(\mathcal{Y}_{v}\mid\sigma_{P_{v}})\geq\left(1-\frac{c_{0}n}{a^{\delta
n^{3\theta/4}}}\right)^{|V_{F}|}\geq 1-\frac{c_{0}n^{1+\theta/12}}{a^{\delta
n^{3\theta/4}}}$

since $|V_{F}|=n^{\theta/12}+2$, and the result follows. ∎

####  5.4.1 Sampling from the degree reducing gadget

We focus now in proving Lemma 5.4. Let $\mu_{G,\beta}$ and $Z_{G,\beta}$ be
the antiferromagnetic Ising distribution and its corresponding partition
function on a degree reducing gadget $G$. We need to show to prove Lemma 5.4
how approximately sample from $\mu_{G,\beta}$ and how to compute $Z_{G,\beta}$
when conditioning on an arbitrary configuration on the ports $P$ of $G$. (Note
that with a slight abuse of notation we are using $P$ for the set of ports of
a single gadget $G$ throughout this section.) Let $\tau\\{+1,-1\\}^{P}$ be a
configuration on the ports. Let $Z_{G,\beta}^{\tau}$ and
$\mu_{G,\beta}^{\tau}$ denote the conditional Ising distribution distribution
and the corresponding partition function.

To establish Lemma 5.4, we provide two different algorithms: one based on the
recent results from [KLR22] that works when $\beta\geq-1/\sqrt{10d}$, and
another based on polymer models that works when $\beta\leq-\frac{c\log d}{d}$
(for a sufficiently large constant $c>0$), so that each value of the regime
$\beta<0$ is covered by one of these algorithms provided $d$ is a large
enough.

Both algorithms use facts about the spectrum of the multi-graph induced by
$V_{G}\setminus P$. Hence, let $H=(V_{H},E_{H})$ be the multi-graph that
results from removing $P$ from $V_{G}$. Let $A_{H}$ be the adjacency matrix
for the multi-graph $H$; that is, $A_{H}(u,v)$ is the multiplicity of the edge
$\\{u,v\\}$ in $H$. For $S\subseteq V_{H}$, let $\partial_{e}(S)$ be the set
of edges from $E_{H}$ with one endpoint in $S$ and one $V_{H}\setminus S$. For
any real symmetric matrix $Q$, let $\lambda_{i}(Q)$ denote its $i$-th largest
eigenvalue.

######  Fact 5.8.

Suppose $d=O(1)$. Then, with probability $1-o(1)$:

  1. 1.

$d-2\sqrt{d}-2\leq\lambda_{1}(A_{H})\leq d+2\sqrt{d}$;

  2. 2.

$-d-2\sqrt{d}\leq\lambda_{|V_{H}|}(A_{H})\leq-d+2\sqrt{d}+2$;

  3. 3.

For $i\geq 2$, $-4\sqrt{d}-2\leq\lambda_{2}(A_{H})\leq 4\sqrt{d}+2$;

  4. 4.

For every $S\subseteq V_{H}$ such that $|S|\leq|V_{H}|/2$, we have
$|\partial_{e}(S)|\geq\frac{d-4\sqrt{d}-2}{2}|S|$.

###### Proof.

Consider the symmetric matrices $A$, $B$, and $T$, of dimension
$|V_{H}|\times|V_{H}|$ defined by:

  * •

$A(u,v)=\kappa$ if $u\in W_{+}\cup U_{+}$ and $v\in W_{-}\cup U_{-}$ (or vice
versa) and the edge $\\{u,v\\}$ appears $\kappa$ times in
$\bigcup_{i=1}^{d-1}M_{i}$; all other entries of $A$ are $0$.

  * •

$B(u,v)=1$ if $u\in W_{+}$ and $v\in W_{-}$ (or vice versa) and $\\{u,v\\}\in
M$; all other entries of $B$ are $0$.

  * •

$T(u,v)=1$ if $\\{u,v\\}\in E_{H}$ and either $u$ or $v$ (or both) are
vertices in $V_{H}\setminus(W_{+}\cup U_{+}\cup W_{-}\cup U_{-})$; all other
entries of $T$ are $0$.

Note that $A_{H}=A+B+T$, so it follows from Weyl’s inequality (see [Fra12])
that

$\lambda_{i}(A)+\lambda_{|V_{H}|}(B)+\lambda_{|V_{H}|}(T)\leq\lambda_{i}(A_{H})\leq\lambda_{i}(A)+\lambda_{1}(B)+\lambda_{1}(T).$

From Theorem 4 in [BDH22] and contiguity (see Theorem 4 and Corollary 1 in
[MRRW97]), we know that $A$ has real eigenvalues
$\lambda_{1}(A)\geq\lambda_{2}(A)\geq\dots\geq\lambda_{|V_{H}|}(A)$, where
$\lambda_{1}(A)=d-1$, $\lambda_{i}(A)=-\lambda_{|V_{H}|-i+1}(A)$, and
$2\sqrt{d}-1\leq\lambda_{2}(A)\leq 2\sqrt{d}+1$ with probability $1-o(1)$. The
matrix $B$ has eigenvalues $1$ and $-1$. Also, all the eigenvalues of the
matrix $T$ are real and belong to the interval $[-2\sqrt{d},2\sqrt{d}]$ (see
[HLW06]). Combining these facts, we obtain parts 1, 2 and 3; part 4 follows
from Cheeger’s inequality (for multi-graphs). ∎

###### Proof of Lemma 5.4.

Let $J$ be a $|V_{H}|\times|V_{H}|$ matrix indexed by the vertices of $H$ with
entries $J(u,v)=\beta\cdot A_{H}(u,v)$ for $u\neq v$ and $J(u,u)=\alpha$ where
$\alpha$ is a real number we choose later. Let $\partial P\subset V_{H}$ be
the set of vertices of $H$ that were incident to $P$ in $G$. Define a magnetic
field $h$ by letting $h_{v}=\beta$ (resp., $h_{v}=-\beta$) if $v\in\partial P$
and the vertex adjacent to $v$ in $P$ has $+1$ (resp., $-1$) spin in $\tau$;
we set $h_{v}=0$ otherwise. The Ising model on $H$ with edge interaction
$\beta$ and external field $h$ assigns to each configuration $\sigma$ on $H$
probability:

$\displaystyle\mu_{H,\beta}(\sigma)$
$\displaystyle=\frac{1}{Z_{H,\beta}}\exp\Big{(}\beta\sum_{\\{u,v\\}\in
E_{H}}\sigma_{u}\sigma_{v}+\sum_{v\in
V_{H}}h_{v}\sigma_{v}\Big{)}=\frac{1}{\hat{Z}_{H,\beta}}\exp\Big{(}\frac{1}{2}\langle\sigma,J\sigma\rangle+\langle
h,\sigma\rangle\Big{)},$ (16)

where $\hat{Z}_{H,\beta}=e^{\alpha|V_{H}|}Z_{H,\beta}$, and we interpret
$\sigma$ and $h$ as vectors indexed by the vertices of $H$. By construction,
$Z_{G,\beta}^{\tau}=Z_{H,\beta}$ and
$\mu_{G,\beta}^{\tau}(\sigma)=\mu_{H,\beta}(\sigma)$ for every
$\sigma\in\\{+,-\\}^{V_{H}}$.

The matrix $J$ has real eigenvalues
$\lambda_{1}(J)\geq\lambda_{2}(A)\geq\dots\geq\lambda_{|V_{H}|}(J)$. To bound
the spectrum of $J$, we note that $J=\beta A_{H}+\alpha I$ and so
$\lambda_{i}(J)=\beta\lambda_{i}(A_{H})+\alpha.$ Hence, setting
$\alpha=-\beta(4\sqrt{d}+2)$ and assuming that $0>\beta\geq-{1}/(10\sqrt{d})$
and that $d$ is sufficiently large, we obtain from Fact 5.8 that with
probability $1-o(1)$: $\lambda_{1}(J)=\Theta(\sqrt{d})$,
$\lambda_{|V(H)|}(J)=-\Theta(\sqrt{d})$ and that every other eigenvalue of $J$
is in the interval $[0,1]$. Then, Theorem 1.1 from [KLR22] implies that:

  1. 1.

There is an algorithm that with probability $1-e^{-{|V_{H}|}}$ produces an
$e^{\varepsilon}$-multiplicative approximation for
$\hat{Z}_{H,\beta}=Z_{G,\beta}^{\tau}$ with running time
$\mathrm{poly}(|V_{H}|,{1}/{\varepsilon})$; and

  2. 2.

There is an algorithm to sample from a distribution within $\varepsilon$ total
variation distance from $\mu_{H,\beta}=\mu_{G,\beta}^{\tau}$ with running time
$\mathrm{poly}(|V_{H}|,\log(1/\varepsilon))$.

Hence, we have established the result for the case when
$\beta\geq-\frac{1}{10\sqrt{d}}$. We consider next the case when
$\beta\leq-\frac{c\log d}{d}$, for a suitably large constant $c>0$. For this,
we introduce the notion of polymer models.

For a fixed configuration $\tau$ in $P$, let $P^{+}\subset\partial P$ be the
set of vertices of $\partial P$ adjacent to a vertex assigned “+” in $\tau$;
define $P^{-}\subset\partial P$ similarly. For a configuration $\sigma$ on
$H$, let $p^{+}(\sigma)$ (resp., $p^{-}(\sigma)$) denote the number of
vertices from $P^{+}$ (resp., $P^{-}$) that are assigned spin $-1$ (resp.
$+1$) in $\sigma$. Let also $D(H,\sigma)$ denote the number of edges incident
two vertices with different spins in $\sigma$. Then, we can renormalize the
Ising distribution Eq. 16 as:

$\mu_{H,\beta}(\sigma)=\frac{1}{\tilde{Z}_{H}}e^{-2\beta(D(H,\sigma)+p^{+}(\sigma)+p^{-}(\sigma))}=:\frac{w(\sigma)}{\tilde{Z}_{H,\beta}},$

where $\tilde{Z}_{H,\beta}=e^{-\beta(|E_{H}|+|\partial P|)}Z_{H,\beta}$.

Let $\Omega=\\{+1,-1\\}^{V_{H}}$. Observe the graph $H$ is bipartite with
partition $(L,R)$ where $L\cup R=V_{H}$ and $|L|=|R|$. Let
$\Omega^{\pm}\subset\Omega$ be the subset of configurations where the number
vertices that are assigned $+1$ in $L$ and $-1$ in $R$ is more than
$|V_{H}|/2$. Define $\Omega^{\mp}$ analogously. Let
$Z_{H}^{\pm}=\sum_{\sigma\in\Omega^{\pm}}w(\sigma)$ and
$Z_{H}^{\mp}=\sum_{\sigma\in\Omega^{-=}}w(\sigma)$ so that
$\tilde{Z}_{H,\beta}=Z_{H}^{\pm}+Z_{H}^{\mp}$. We define a polymer model whose
partition function will serve as a good approximation for $Z_{H}^{\pm}$ and
$Z_{H}^{\mp}$.

We say $\gamma\subset V_{H}$ is a polymer if the subgraph induced by $\gamma$
is connected and $|\gamma|<|V_{H}|/2$. Two polymers are compatible if the
graph distance between them is at least $2$. Let $\mathcal{G}$ be the family
of all sets of mutually compatible polymers. To each polymer $\gamma$ we
assign the weight:

$w_{\gamma}=e^{-2\beta(-|\partial_{e}(\gamma)|+|P^{-}\cap
L\cap\gamma|+|P^{+}\cap R\cap\gamma|-|P^{+}\cap L\cap\gamma|-|P^{-}\cap
R\cap\gamma|)}.$

Define the polymer partition function:

$\Phi=\sum_{\Gamma\in\mathcal{G}}\prod_{\gamma\in\Gamma}w_{\gamma}.$

We say $S\subset V_{H}$ is sparse if every connected component of $S$ has size
less than $|V_{H}|/2$. Note that there is a one-to-one correspondence between
the sparse subsets of $V_{H}$ and polymer configurations from $\mathcal{G}$.
Then:

$\displaystyle\hat{\Phi}$ $\displaystyle:=e^{-2\beta(|E_{H}|+|P^{-}\cap
R|+|P^{+}\cap L|)}\cdot\Phi$ $\displaystyle=e^{-2\beta(|E_{H}|+|P^{-}\cap
R|+|P^{+}\cap
L|)}\sum_{\Gamma\in\mathcal{G}}\prod_{\gamma\in\Gamma}w_{\gamma}$
$\displaystyle=\sum_{S~{}\text{sparse}}e^{-2\beta(|E_{H}|-|\partial_{e}(S)|+|P^{-}\cap
R|+|P^{+}\cap L|+|P^{-}\cap L\cap S|+|P^{+}\cap R\cap S|-|P^{+}\cap L\cap
S|-|P^{-}\cap R\cap S|)}$
$\displaystyle=\sum_{S~{}\text{sparse}}e^{-2\beta(|E_{H}|-|\partial_{e}(S)|+|((R\setminus
S)\cup(S\cap L))\cap P^{-}|+|((L\setminus S)\cup(S\cap R))\cap P^{+}|)}$

Now, we say $S\subset V_{H}$ is small if $|S|<|V_{H}|/2$ (otherwise we say it
is large), so that

$Z_{H}^{\mp}=\sum_{S~{}\text{small}}e^{-2\beta(|E_{H}|-|\partial_{e}(S)|+|((R\setminus
S)\cup(S\cap L))\cap P^{-}|+|((L\setminus S)\cup(S\cap R))\cap P^{+}|)}.$

Hence,

$0\leq\hat{\Phi}-Z_{H}^{\mp}\leq\sum_{S~{}\text{sparse,
large}}e^{-2\beta(|E_{H}|-|\partial_{e}(S)|+|((R\setminus S)\cup(S\cap L))\cap
P^{-}|+|((L\setminus S)\cup(S\cap R))\cap P^{+}|)}.$

If $S$ is sparse, by part 4 of Fact 5.8, each connected component $S_{i}$ of
$S$ satisfies $\partial_{e}(S_{i})\geq\theta|S_{i}|$ with
$\theta=\frac{d-4\sqrt{d}-2}{2}$. Summing over the components of $S$ we get
$\partial_{e}(S)\geq\theta|S|\geq\theta|V_{H}|/2$ when $S$ is large. Then,

$\displaystyle|\hat{\Phi}-Z_{H}^{\mp}|$
$\displaystyle\leq\sum_{S~{}\text{sparse,
large}}e^{-2\beta(|E_{H}|-\theta|V_{H}|/2+|((R\setminus S)\cup(S\cap L))\cap
P^{-}|+|((L\setminus S)\cup(S\cap R))\cap P^{+}|)}$

and since $Z_{H}^{\mp}\geq e^{-2\beta(|E_{H}|+|L\cap P^{+}|+|R\cap P^{-}|)}$
and $|S|<|V_{H}|/2$, we have

$\left|1-\frac{\hat{\Phi}}{Z_{H}^{\mp}}\right|\leq
2^{|V_{H}|}e^{-2\beta(-\theta|V_{H}|/2+|V_{H}|/2)}\leq e^{-|V_{H}|},$ (17)

provided $\theta>1$ and $-\beta\geq\frac{1+\ln 2}{\theta-1}$. An analogous
argument yields the same bound for $Z_{H}^{\pm}$.

Our goal now is to use Theorem 8 from [JKP20] to obtain an approximation for
$\Phi$ and consequently for $\hat{\Phi}$, $Z_{H}^{\mp}$, $Z_{H}^{\pm}$ and
ultimately for $Z_{H,\beta}=Z_{H}^{\pm}+Z_{H}^{\mp}$. For this, it suffices to
check that our polymer model satisfies the so-called Kotecký-Preiss condition
(see, e.g., equation (3) from [JKP20]). This condition requires that for every
polymer $\gamma$:

$\sum_{\gamma^{\prime}:d(\gamma,\gamma^{\prime})\leq
1}w_{\gamma^{\prime}}e^{2|\gamma^{\prime}|}\leq|\gamma|,$ (18)

where $d(\cdot,\cdot)$ denotes graph distance. First note that

$w_{\gamma^{\prime}}=e^{-2\beta(-|\partial_{e}(\gamma^{\prime})|+|P^{-}\cap
L\cap\gamma^{\prime}|+|P^{+}\cap R\cap\gamma^{\prime}|-|P^{+}\cap
L\cap\gamma^{\prime}|-|P^{-}\cap R\cap\gamma^{\prime}|)}\leq
e^{-2\beta(-\theta/2+1)|\gamma^{\prime}|}.$

Hence,

$\displaystyle\sum_{\gamma^{\prime}:d(\gamma,\gamma^{\prime})\leq
1}w_{\gamma^{\prime}}e^{2|\gamma^{\prime}|}$
$\displaystyle\leq\sum_{\gamma^{\prime}:d(\gamma,\gamma^{\prime})\leq
1}e^{|\gamma^{\prime}|(2-2\beta(-\theta/2+1))}\leq\sum_{v\in\gamma\cup\partial_{v}(\gamma)}\,\sum_{\gamma^{\prime}:v\in\gamma^{\prime}}e^{|\gamma^{\prime}|(2-2\beta(-\theta/2+1))}.$

The number of polymers of size $k$ that contain a given vertex is at most
$(ed)^{k}$ (see Lemma 2.1 in [GK04]), so

$\sum_{\gamma^{\prime}:v\in\gamma^{\prime}}e^{|\gamma^{\prime}|(2-2\beta(-\theta/2+1))}\leq\sum_{t\geq
1}\big{(}de^{(3-2\beta(-\theta/2+1))}\big{)}^{t}\leq\frac{1}{d+1}$

when $-\beta\geq\frac{3+\ln(d(d+2))}{\theta-2}$ and $\theta>2$. (Note that the
latter is true when $d$ is large enough.) Since
$|\gamma\cup\partial_{v}(\gamma)|\leq(d+1)|\gamma|$, Eq. 18 follows. Hence,
for sufficiently large $d=O(1)$, for a suitable constant $c>0$, Theorem 8 from
[JKP20] gives an FPTAS for $\Phi$ when $-\beta\geq\frac{c\ln d}{d}$. This
yields the desired FPTAS for $Z_{H,\beta}$. Note that if the desired
approximation factor is smaller than $e^{-|V_{H}|}$, which is the best
approximation for $Z_{H,\beta}$ we could using the polymer function $\Phi$
(see Eq. 17), then we could use instead brute force for counting and sampling,
since the running time would be allowed to be exponential in $|V_{H}|$.
Finally, Theorem 9 from [JKP20] gives the a polynomial-time approximate
sampling algorithm for the distribution:

$\nu(\Gamma)=\frac{\prod_{\gamma\in\Gamma}w_{\gamma}}{\Phi}.$

Once a polymer configuration $\Gamma$ is sampled from $\nu$, it can be easily
transformed into an Ising configuration by setting the vertices in
$L\setminus\Gamma$ and $R\cap\Gamma$ to $+1$ with probability
$\frac{Z_{H}^{\pm}}{Z_{H}^{\pm}+Z_{H}^{\mp}}$ and all other vertices to $-1$,
and doing the opposite with the remaining probability. ∎

##  6 Statistical Lower Bounds

In this section we establish lower bounds on the number of samples required to
perform uniformity testing over the hypercube $\\{0,1\\}^{n}$ (i.e., $k=2$),
with a focus on comparisons between testing for KL divergence and TV distance,
and between testing with $\mathsf{Coordinate\ Oracle}+\mathsf{General\
Oracle}$ and $\mathsf{Subcube\ Oracle}$. Throughout this section, we assume
$k=2$ and $\mathcal{K}=\\{0,1\\}$. Let $u_{n}$ denote the uniform distribution
over $\mathcal{X}_{n}=\\{0,1\\}^{n}$ for an integer $n\in\mathbb{N}^{+}$. We
omit the subscript $n$ when it is clear from context.

Our proofs of theorems use the recipe given in [CRS15, Theorem 8] for showing
sample lower bounds with the pairwise conditional sampling oracle. We also
note that the arguments here and in [CRS15] are similar to the _hybrid
argument_ in cryptography.

###  6.1 Uniformity testing with $\mathsf{Subcube\ Oracle}$ for KL divergence

In this subsection we consider uniformity testing over $\\{0,1\\}^{n}$ with
access to $\mathsf{Subcube\ Oracle}$ for KL divergence, and give an
information-theoretic lower bound of $\Omega(n/\varepsilon)$ on the number of
samples needed.

Let $\mathsf{Alg}$ denote an arbitrary uniformity testing algorithm (possibly
randomized and adaptive), and for simplicity let $\mathsf{Ora}[\pi]$ denote
the $\mathsf{Subcube\ Oracle}$ with respect to a distribution $\pi$ over
$\\{0,1\\}^{n}$. A _pinning_ $\tau$ is a partial configuration on a subset of
coordinates, namely $\tau\in\\{0,1\\}^{\Lambda}$ where $\Lambda\subseteq[n]$.
Observe that pinnings are exactly the inputs to the subcube oracle
$\mathsf{Ora}[\pi]$. Let $\mathcal{T}$ be the collection of all pinnings on
all subsets of coordinates. For $L\in\mathbb{N}^{+}$, define the _query
history_ with respect to $\mathsf{Alg}$ and $\mathsf{Ora}[\pi]$ of length $L$
to be the random vector in $(\mathcal{T}\times\\{0,1\\}^{n})^{L}$ generated as
follows:

  * •

For $i=1,\dots,L$:

    * –

$\mathsf{Alg}$ receives
$\left((\tau_{1},x_{1}),\dots,(\tau_{i-1},x_{i-1})\right)$ as input and
generates $\tau_{i}\in\mathcal{T}$ (randomly) as output;

    * –

$\mathsf{Ora}[\pi]$ receives $\tau_{i}$ as input and generates
$x_{i}\in\\{0,1\\}^{n}$ as output.

  * •

The query history is $H=\left((\tau_{1},x_{1}),\dots,(\tau_{L},x_{L})\right)$.

The $\mathsf{output}$ of $\mathsf{Alg}$ with sample complexity $L$ is a
(randomized) function of the query history $H$ of length $L$.

Our main theorem is stated as below in terms of the query history, from which
Theorem 1.4 follows immediately.

######  Theorem 6.1.

Let $n\in\mathbb{N}^{+}$ be a sufficiently large integer and $\varepsilon>0$
be a real. Let $u=u_{n}$ denote the uniform distribution over $\\{0,1\\}^{n}$.
There is no algorithm which can achieve the following properties using only
$L\leq n/(64\varepsilon)$ samples:

  * •

$\Pr_{H}\left(\mathsf{output}=\mathsf{Yes}\right)\geq 2/3$ for a random query
history $H$ of length $L$ with respect to $\mathsf{Alg}$ and
$\mathsf{Ora}[u]$;

  * •

$\Pr_{H^{\prime}}\left(\mathsf{output}=\mathsf{No}\right)\geq 2/3$ for a
random query history $H^{\prime}$ of length $L$ with respect to $\mathsf{Alg}$
and $\mathsf{Ora}[\pi]$ where $\pi$ is any distribution such that
$D_{\mathrm{KL}}\left(\pi\,\|\,u\right)\geq\varepsilon$.

Our plan, as in many previous works, is to construct a family $\mathcal{B}$ of
bad distributions that are all $\varepsilon$ far away from $u$ in KL
divergence, such that when picking a bad distribution from $\mathcal{B}$
uniformly at random and drawing limited number of samples, the joint
distributions of these samples are close to that of samples draw from $u$. We
present now our construction of the bad family $\mathcal{B}$. Let
$t=\left\lceil\log_{2}(n/\varepsilon)\right\rceil-3$ for sufficiently large
$n$. For any $A\subseteq[n]$ with $|A|=t$ and any $\sigma\in\\{0,1\\}^{n}$,
define the distribution $\pi_{A,\sigma}$ in the following way. A sample from
$\pi_{A,\sigma}$ is generated by:

  * •

For each $i\in A$ independently sample $x_{i}\in\\{0,1\\}$ uniformly at
random;

  * •

If $x_{A}\neq\sigma_{A}$, then for each $j\in[n]\setminus A$ independently
sample $x_{j}\in\\{0,1\\}$ uniformly at random and output $x$;

  * •

If $X_{A}=\sigma_{A}$ then output $x=\sigma$.

We remark that all steps are independent. Finally, we define

$\mathcal{B}=\left\\{\pi_{A,\sigma}:A\in\binom{[n]}{t},\sigma\in\\{0,1\\}^{n}\right\\}.$

We first show that the distributions in $\mathcal{B}$ are all bad in the sense
that their KL divergence to the uniform distribution is at least
$\varepsilon$. A key intuition in our construction of $\pi_{A,\sigma}$ here is
that while the KL divergence
$D_{\mathrm{KL}}\left(\pi_{A,\sigma}\,\|\,u\right)=\Theta(\varepsilon)$, the
TV distance is much smaller than $\varepsilon$ and is
$d_{\mathrm{TV}}\left(\pi_{A,\sigma},u\right)=\Theta(2^{-t})=\Theta(\varepsilon/n)$.
Hence, intuitively, it will take
$\Theta(1/d_{\mathrm{TV}}\left(\pi,u\right))=\Theta(n/\varepsilon)$ samples to
test between the family $\mathcal{B}$ and the uniform distribution $u$.

######  Claim 6.2.

For all $\pi\in\mathcal{B}$ one has

$D_{\mathrm{KL}}\left(\pi\,\|\,u\right)\geq\varepsilon.$

###### Proof.

Suppose $\pi=\pi_{A,\sigma}\in\mathcal{B}$ is a bad distribution. By
definition we have $\pi(x)=u(x)=2^{-n}$ if $x_{A}\neq\sigma_{A}$, and
$\pi(\sigma)=2^{-t}$. Hence, we get

$D_{\mathrm{KL}}\left(\pi\,\|\,u\right)=\pi(\sigma)\ln\left(\frac{\pi(\sigma)}{u(\sigma)}\right)=\frac{\ln
2}{2^{t}}(n-t)\geq\frac{2\varepsilon}{n}(n-t)\geq\varepsilon,$

for $n$ sufficiently large. ∎

Define $H$ to be the random query history of length $L$ with respect to
$\mathsf{Alg}$ and $\mathsf{Ora}[u]$, and let $\mathsf{output}$ denote the
random output with respect to $H$ and $\mathsf{Alg}$. Define $H^{\prime}$ to
be the random query history of length $L$ generated by

  * •

Pick $\pi\in\mathcal{B}$ uniformly at random;

  * •

Let $H^{\prime}$ be the random query history of length $L$ with respect to
$\mathsf{Alg}$ and $\mathsf{Ora}[\pi]$.

Further, let $\mathsf{output}^{\prime}$ denote the random output with respect
to $H^{\prime}$ and $\mathsf{Alg}$. Our goal is to show that the TV distance
between the two query histories $H$ and $H^{\prime}$ is small and therefore by
the data processing inequality the TV distance between $\mathsf{output}$ and
$\mathsf{output}^{\prime}$ is also small so the two properties in Theorem 6.1
cannot simultaneously hold.

######  Lemma 6.3.

For the family $\mathcal{B}$ of bad distributions, query histories
$H,H^{\prime}$ of length $L\leq n/(64\varepsilon)$, and
$\mathsf{output},\mathsf{output}^{\prime}$ defined as above, we have

$d_{\mathrm{TV}}\left(\mathsf{output},\mathsf{output}^{\prime}\right)\leq
d_{\mathrm{TV}}\left(H,H^{\prime}\right)\leq\frac{1}{4}.$

We present next the proof of Theorem 6.1 provided Lemma 6.3. The proof of the
latter is postponed to Section 6.1.1.

###### Proof of Theorem 6.1.

Suppose for sake of contradiction that $\mathsf{Alg}$ satisfies both
properties as in Theorem 6.1. Then for the family $\mathcal{B}$ of bad
distributions, query histories $H,H^{\prime}$ of length $L\leq
n/(64\varepsilon)$, and $\mathsf{output},\mathsf{output}^{\prime}$ defined as
above, we know from these two properties that

$\Pr\nolimits\left(\mathsf{output}=\mathsf{Yes}\right)\geq
2/3\quad\text{and}\quad\Pr\nolimits\left(\mathsf{output}^{\prime}=\mathsf{Yes}\right)\leq
1/3.$

This implies
$d_{\mathrm{TV}}\left(\mathsf{output},\mathsf{output}^{\prime}\right)\geq 1/3$
which contradicts Lemma 6.3. ∎

####  6.1.1 Proof of Lemma 6.3

To prove the lemma, we use the hybrid argument in cryptography which was
already applied in previous works [CRS15]. For $0\leq\ell\leq L$, define the
_hybrid query history_ $H^{(\ell)}$ with respect to $\mathsf{Alg}$,
$\mathsf{Ora}[u]$, and $\mathsf{Ora}[\pi]$ to be the random vector in
$(\mathcal{T}\times\\{0,1\\}^{n})^{L}$ generated as follows:

  * •

For $i=1,\dots,\ell$:

    * –

$\mathsf{Alg}$ receives
$\left((\tau_{1},x_{1}),\dots,(\tau_{i-1},x_{i-1})\right)$ as input and
generates $\tau_{i}\in\mathcal{T}$ (randomly) as output;

    * –

$\mathsf{Ora}[u]$ receives $\tau_{i}$ as input and generates
$x_{i}\in\\{0,1\\}^{n}$ as output.

  * •

Pick $\pi\in\mathcal{B}$ uniformly at random;

  * •

For $i=\ell+1,\dots,L$:

    * –

$\mathsf{Alg}$ receives
$\left((\tau_{1},x_{1}),\dots,(\tau_{i-1},x_{i-1})\right)$ as input and
generates $\tau_{i}\in\mathcal{T}$ (randomly) as output;

    * –

$\mathsf{Ora}[\pi]$ receives $\tau_{i}$ as input and generates
$x_{i}\in\\{0,1\\}^{n}$ as output.

  * •

The hybrid query history is
$H^{(i)}=\left((\tau_{1},x_{1}),\dots,(\tau_{L},x_{L})\right)$.

Observe that $H^{(0)}=H^{\prime}$ and $H^{(L)}=H$ in distribution. We will
prove the following lemma regarding the distance between two adjacent hybrid
query histories.

######  Lemma 6.4.

For every $1\leq\ell\leq L$, we have

$d_{\mathrm{TV}}\left(H^{(\ell-1)},H^{(\ell)}\right)\leq\frac{16\varepsilon}{n}.$

Note that Lemma 6.3 is an immediate consequence of Lemma 6.4.

###### Proof of Lemma 6.3.

By the triangle inequality and Lemma 6.4, we have that

$d_{\mathrm{TV}}\left(H,H^{\prime}\right)\leq\sum_{\ell=1}^{L}d_{\mathrm{TV}}\left(H^{(\ell-1)},H^{(\ell)}\right)\leq
L\cdot\frac{16\varepsilon}{n}\leq\frac{1}{4},$

as claimed. ∎

It remains to prove Lemma 6.4. Inspecting the definitions of $H^{(\ell-1)}$
and $H^{(\ell)}$, we see that they only differ locally at one place, which we
describes as follows. For $0\leq i\leq L$ let
$H_{i}=\left((\tau_{1},x_{1}),\dots,(\tau_{i},x_{i})\right)$ denote the first
$i$ entries of a random hybrid query history (notice that $H_{0}=\emptyset$).
We write $H^{(\ell-1)}$ and $H^{(\ell)}$ in the following form.

  1. Generation of $H^{(\ell-1)}$:

  2. (1)

$H_{0}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[u]}H_{\ell-1}$;

  3. (2)

$\pi\sim\mathrm{unif}(\mathcal{B})$;

  4. (3)

$H_{\ell-1}\xrightarrow{\mathsf{Alg}}\tau_{\ell}\xrightarrow{\mathsf{Ora}[\pi]}x_{\ell}$;

  5. (4)

$H_{\ell}\leftarrow H_{\ell-1}$ append $(\tau_{\ell},x_{\ell})$;

  6. (5)

$H_{\ell}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[\pi]}H_{L}=H^{(\ell-1)}$.

  7. Generation of $H^{(\ell)}$:

  8. (1)

$H_{0}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[u]}H_{\ell-1}$;

  9. (2)

$H_{\ell-1}\xrightarrow{\mathsf{Alg}}\tau_{\ell}\xrightarrow{\mathsf{Ora}[u]}x_{\ell}$;

  10. (3)

$H_{\ell}\leftarrow H_{\ell-1}$ append $(\tau_{\ell},x_{\ell})$;

  11. (4)

$\pi\sim\mathrm{unif}(\mathcal{B})$;

  12. (5)

$H_{\ell}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[\pi]}H_{L}=H^{(\ell)}$.

In fact the ordering of the steps (2)-(4) can be changed appropriately without
having any influence on the final distribution of both $H^{(\ell-1)}$ and
$H^{(\ell)}$, which will be helpful for a coupling argument. We rewrite the
generating processes of $H^{(\ell-1)}$ and $H^{(\ell)}$ equivalently as
follows:

  1. Generation of $H^{(\ell-1)}$:

  2. (1)

$H_{0}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[u]}H_{\ell-1}$;

  3. (2)

$H_{\ell-1}\xrightarrow{\mathsf{Alg}}\tau_{\ell}$;

  4. (3)

$\pi\sim\mathrm{unif}(\mathcal{B})$,
$\tau_{\ell}\xrightarrow{\mathsf{Ora}[\pi]}x_{\ell}$;

  5. (4)

$H_{\ell}\leftarrow H_{\ell-1}$ append $(\tau_{\ell},x_{\ell})$;

  6. (5)

$H_{\ell}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[\pi]}H_{L}=H^{(\ell-1)}$.

  7. Generation of $H^{(\ell)}$:

  8. (1)

$H_{0}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[u]}H_{\ell-1}$;

  9. (2)

$H_{\ell-1}\xrightarrow{\mathsf{Alg}}\tau_{\ell}$;

  10. (3)

$\pi\sim\mathrm{unif}(\mathcal{B})$,
$\tau_{\ell}\xrightarrow{\mathsf{Ora}[u]}x_{\ell}$;

  11. (4)

$H_{\ell}\leftarrow H_{\ell-1}$ append $(\tau_{\ell},x_{\ell})$;

  12. (5)

$H_{\ell}\xrightarrow{\mathsf{Alg},\,\mathsf{Ora}[\pi]}H_{L}=H^{(\ell)}$.

Note that before and after the third step, the two processes have exactly the
same steps. In the third step for $H^{(\ell-1)}$, we pick a bad distribution
$\pi\in\mathcal{B}$ uniformly at random, and $\mathsf{Ora}[\pi]$ receives the
pinning $\tau_{\ell}$ as input and generates $x_{\ell}\in\\{0,1\\}^{n}$
according to $\pi$ conditioned on $\tau_{\ell}$. Meanwhile, in the third step
for $H^{(\ell)}$, we still pick a bad distribution $\pi\in\mathcal{B}$ but do
not use it (for now), and $\mathsf{Ora}[u]$ receives $\tau_{\ell}$ as input
and generates $x_{\ell}\in\\{0,1\\}^{n}$ according to $u$ instead of $\pi$. It
is enough to show that, in this step, conditional on that $H_{\ell-1}$ and
$\tau_{\ell}$ are the same, the $x_{\ell}$ generated in the two processes are
the same with high probability. Since before and after this step the two
processes are doing the same thing, we can then couple these two processes to
produce the same hybrid query history with high probability, i.e.,
$H^{(\ell-1)}=H^{(\ell)}$.

The following technical lemma bounds the probability that $x_{\ell}$’s are the
same in both processes in the third step, which is crucial to us as explained
earlier. The proof of it can be found in Section 6.1.2.

######  Lemma 6.5.

Let $\tau\in\mathcal{T}$ be an arbitrary pinning on some subset
$\Lambda\subseteq V$ of size $m$. Then for a random distribution $\pi$ chosen
uniformly at random from $\mathcal{B}$, we have

$\mathbb{E}_{\pi\sim\mathrm{unif}(\mathcal{B})}\left[d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi\left(\cdot\mid\tau\right)\right)\right]\leq\frac{16\varepsilon}{n}.$

We give below the proof of Lemma 6.4.

###### Proof of Lemma 6.4.

We construct a coupling of $H^{(\ell-1)}$ and $H^{(\ell)}$ via coupling step-
by-step the two processes generating $H^{(\ell-1)}$ and $H^{(\ell)}$.
Initially $H_{0}=\emptyset$ for both processes. Then we can couple
$H_{\ell-1}$ and $\tau_{\ell}$ since they are generated in the same way in
both processes. For the third step, the bad distribution $\pi$ can be chosen
to be the same and we deduce from Lemma 6.5 that $x_{\ell}$’s can be coupled
with probability at least $1-\varepsilon/n$. After that, suppose we couple
$x_{\ell}$, $H_{\ell}$ and then the final outputs are coupled. Hence, for this
coupling $\mathbb{P}$ we have

$d_{\mathrm{TV}}\left(H^{(\ell-1)},H^{(\ell)}\right)\leq\mathbb{P}\left(H^{(\ell-1)}\neq
H^{(\ell)}\right)\leq\frac{16\varepsilon}{n},$

as wanted. ∎

####  6.1.2 Proof of Lemma 6.5

Here we give the proof of the technical lemma, Lemma 6.5.

###### Proof of Lemma 6.5.

The distribution $\pi\in\mathcal{B}$ depends on $A$ and $\sigma$. We will show
that for any choice of $A\in\binom{[n]}{t}$ one has

$\mathbb{E}_{\sigma}\left[d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi_{A,\sigma}\left(\cdot\mid\tau\right)\right)\right]\leq\frac{16\varepsilon}{n},$

where $\sigma$ is a uniformly random configuration in $\\{0,1\\}^{n}$.

Suppose $|\Lambda|=\ell$. Suppose $|A\cap\Lambda|=j$ and hence
$|A\setminus\Lambda|=t-j$. Notice that $j\leq\min\\{t,\ell\\}$. We partition
$\mathcal{X}=\\{0,1\\}^{n}$ into three disjoint subsets.

Case 1.
$\mathcal{X}_{1}=\\{\sigma\in\\{0,1\\}^{n}:\sigma_{A\cap\Lambda}\neq\tau_{A\cap\Lambda}\\}$.
We have

$\Pr\left(\sigma\in\mathcal{X}_{1}\right)=\frac{|\mathcal{X}_{1}|}{2^{n}}=1-\frac{1}{2^{j}},$

and also

$d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi_{A,\sigma}\left(\cdot\mid\tau\right)\right)=0,\quad\forall\sigma\in\mathcal{X}_{1}.$

Case 2.
$\mathcal{X}_{2}=\\{\sigma\in\\{0,1\\}^{n}:\sigma_{A\cap\Lambda}=\tau_{A\cap\Lambda},\,\sigma_{\Lambda\setminus
A}\neq\tau_{\Lambda\setminus A}\\}$. We have

$\Pr\nolimits_{\sigma}\left(\sigma\in\mathcal{X}_{2}\right)=\frac{|\mathcal{X}_{2}|}{2^{n}}=\frac{1}{2^{j}}-\frac{1}{2^{\ell}}.$

By definition we have

$\pi_{A,\sigma}\left(x\mid\tau\right)=\begin{cases}0,&\text{if}~{}x_{A\setminus\Lambda}=\sigma_{A\setminus\Lambda};\\\
\dfrac{1}{2^{n-\ell}-2^{n-\ell-t+j}},&\text{if}~{}x_{A\setminus\Lambda}\neq\sigma_{A\setminus\Lambda}.\end{cases}$

It follows that

$d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi_{A,\sigma}\left(\cdot\mid\tau\right)\right)=\frac{1}{2^{t-j}},\quad\forall\sigma\in\mathcal{X}_{2}.$

Case 3.
$\mathcal{X}_{3}=\\{\sigma\in\\{0,1\\}^{n}:\sigma_{\Lambda}=\tau_{\Lambda}\\}$.
We have

$\Pr\nolimits_{\sigma}\left(\sigma\in\mathcal{X}_{3}\right)=\frac{|\mathcal{X}_{3}|}{2^{n}}=\frac{1}{2^{\ell}}.$

By definition we have

$\pi_{A,\sigma}\left(x\mid\tau\right)=\begin{cases}\dfrac{\frac{1}{2^{n}}}{\frac{1}{2^{t}}+\frac{1}{2^{\ell}}-\frac{1}{2^{t+\ell-j}}},&\text{if}~{}x_{A\setminus\Lambda}\neq\sigma_{A\setminus\Lambda};\\\
0,&\text{if}~{}x_{A\setminus\Lambda}=\sigma_{A\setminus\Lambda}~{}\text{and}~{}x_{[n]\setminus\Lambda\setminus
A}\neq\sigma_{[n]\setminus\Lambda\setminus A};\\\
\dfrac{\frac{1}{2^{t}}}{\frac{1}{2^{t}}+\frac{1}{2^{\ell}}-\frac{1}{2^{t+\ell-j}}},&\text{if}~{}x_{[n]\setminus\Lambda}=\sigma_{[n]\setminus\Lambda}.\end{cases}$

It follows that

$d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi_{A,\sigma}\left(\cdot\mid\tau\right)\right)=\frac{\frac{1}{2^{t}}}{\frac{1}{2^{t}}+\frac{1}{2^{\ell}}-\frac{1}{2^{t+\ell-j}}}-\frac{1}{2^{n-\ell}}=\frac{2^{\ell}}{2^{t}+2^{\ell}-2^{j}}-\frac{1}{2^{n-\ell}},\quad\forall\sigma\in\mathcal{X}_{3}.$

Therefore, combining all three cases we get from the law of total expectation
that

$\displaystyle\mathbb{E}_{\sigma}\left[d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi_{A,\sigma}\left(\cdot\mid\tau\right)\right)\right]$
$\displaystyle=\left(1-\frac{1}{2^{j}}\right)0+\left(\frac{1}{2^{j}}-\frac{1}{2^{\ell}}\right)\frac{1}{2^{t-j}}+\frac{1}{2^{\ell}}\left(\frac{2^{\ell}}{2^{t}+2^{\ell}-2^{j}}-\frac{1}{2^{n-\ell}}\right)$
$\displaystyle\leq\frac{1}{2^{t}}+\frac{1}{2^{t}+2^{\ell}-2^{j}}.$

Note that the second term is monotone increasing in $j$ and by definition
$j\leq\min\\{t,\ell\\}$. Hence, we deduce that

$\frac{1}{2^{t}+2^{\ell}-2^{j}}\leq\frac{1}{2^{t}+2^{\ell}-2^{\min\\{t,\ell\\}}}=\frac{1}{2^{\max\\{t,\ell\\}}}\leq\frac{1}{2^{t}}.$

We conclude that for any $A$,

$\mathbb{E}_{\sigma}\left[d_{\mathrm{TV}}\left(u\left(\cdot\mid\tau\right),\pi_{A,\sigma}\left(\cdot\mid\tau\right)\right)\right]\leq\frac{1}{2^{t-1}}\leq\frac{16\varepsilon}{n},$

where in the last inequality we recall that
$t=\left\lceil\log_{2}(n/\varepsilon)\right\rceil-3\geq\log_{2}(n/\varepsilon)-3$.
∎

###  6.2 Uniformity testing with $\mathsf{Coordinate\ Oracle}$ and
$\mathsf{General\ Oracle}$ for TV distance

In this section we consider uniformity testing over the binary hypercube for
TV distance when we have access to $\mathsf{Coordinate\ Oracle}$ and
$\mathsf{General\ Oracle}$. We assume the binary hypercube is denoted by
$\mathcal{X}_{n}=\\{+1,-1\\}^{n}$ instead of $\\{0,1\\}^{n}$, since our bad
distributions will be Ising models where $+1,-1$ are more often used.

Let $\mathsf{Alg}$ denote an arbitrary uniformity testing algorithm (possibly
randomized and adaptive) with $\mathsf{Coordinate\ Oracle}$ and
$\mathsf{General\ Oracle}$ access. We assume that $\mathsf{Alg}$ receives $L$
independent full samples from the $\mathsf{General\ Oracle}$, and is allowed
to make $L$ queries to the $\mathsf{Coordinate\ Oracle}$. Let $\mathcal{T}$
denote the set of all pinnings on $n-1$ coordinates, which is exactly all
possible inputs to the $\mathsf{Coordinate\ Oracle}$. For ease of notation we
denote by $\mathsf{Ora}[\pi]$ the $\mathsf{Subcube\ Oracle}$ with respect to a
distribution $\pi$ over $\\{+1,-1\\}^{n}$. For integer $L\in\mathbb{N}^{+}$,
we define the _query history_ with respect to $\mathsf{Alg}$ and
$\mathsf{Ora}[\pi]$ of length $2L$ to be the random vector in
$\mathcal{X}_{n}^{L}\times(\mathcal{T}\times\\{0,1\\})^{L}$ generated as
follows:

  * •

Let $x_{1},\dots,x_{L}$ be $L$ independent samples from $\pi$;

  * •

For $i=1,\dots,L$:

    * –

$\mathsf{Alg}$ receives
$\left((\tau_{1},a_{1}),\dots,(\tau_{i-1},a_{i-1})\right)$ as input and
generates $\tau_{i}\in\mathcal{T}$ (randomly) as output;

    * –

$\mathsf{Ora}[\pi]$ receives $\tau_{i}$ as input and generates
$a_{i}\in\\{0,1\\}$ as output.

  * •

The query history is
$H=\left(x_{1},\dots,x_{L};(\tau_{1},a_{1}),\dots,(\tau_{L},a_{L})\right)$.

The $\mathsf{output}$ of $\mathsf{Alg}$ with sample complexity $2L$ is a
(randomized) function of the query history $H$ of length $2L$. Our main
theorem is then stated as follows.

######  Theorem 6.6.

There exists a universal constant $c>0$ such that the following holds. Let
$n\in\mathbb{N}^{+}$ be a sufficiently large integer and $\varepsilon>0$ be a
real. Let $u=u_{n}$ denote the uniform distribution over $\\{+1,-1\\}^{n}$.
Then there is no algorithm which can achieve the following properties using
$L$ samples from $\mathsf{General\ Oracle}$ and $L$ queries from
$\mathsf{Coordinate\ Oracle}$ where $L\leq cn/\varepsilon^{2}$:

  * •

$\Pr_{H}\left(\mathsf{output}=\mathsf{Yes}\right)\geq 2/3$ for a random query
history $H$ of length $2L$ with respect to $\mathsf{Alg}$ and
$\mathsf{Ora}[u]$;

  * •

$\Pr_{H^{\prime}}\left(\mathsf{output}=\mathsf{No}\right)\geq 2/3$ for a
random query history $H^{\prime}$ of length $2L$ with respect to
$\mathsf{Alg}$ and $\mathsf{Ora}[\pi]$ where $\pi$ is any distribution such
that $d_{\mathrm{TV}}\left(\pi,u\right)\geq\varepsilon$.

We observe that Theorem 1.5 follows immediately from Theorem 6.6.

In [DDK19, Theorem 14] it was shown that $\Omega(n/\varepsilon^{2})$ samples
are necessary for uniformity testing with only $\mathsf{General\ Oracle}$
access but assuming the hidden distribution $\pi$ is an Ising model. See also
[CDKS20, Theorem 14] for very similar lower bounds in the setting of Bayesian
networks. Note that though Theorem 14 from [DDK19] is stated for _symmetric_
KL divergence, it actually works for TV distance as well, see [DDK19, Remark
4]. We use the same constructions from [DDK19, CDKS20] for the family of bad
distributions for our purpose. Assume that $n$ is even; the case of odd $n$
can be easily reduced to even $n$ by adding an extra uniform, independent
coordinate. Suppose $M$ is a perfect matching of $n$ coordinates, i.e., $M$ is
a collection of $n/2$ pairs of coordinates such that each coordinate appears
in exactly one pair. Let $\mathcal{M}$ be the set of all perfect matchings on
$[n]$. Each bad distribution $\pi_{M}$ where $M\in\mathcal{M}$ corresponds to
an Ising model on the graph $G=([n],M)$ of $n/2$ edges, with the edge coupling
set to be $\beta=\rho\varepsilon/\sqrt{n}$ where $\rho$ is a universal
constant sufficiently large. The following are established in [CDKS20, DDK19].

######  Claim 6.7 ([CDKS20, DDK19]).

  1. (1)

For $\rho>0$ sufficiently large, for all $M\in\mathcal{M}$, it holds

$d_{\mathrm{TV}}\left(\pi_{M},u\right)\geq\varepsilon.$

  2. (2)

For any $\rho>0$ there exists $c_{1}=c_{1}(\rho)>0$ such that the following
holds. Suppose $L\leq c_{1}n/\varepsilon$. Let $X=(x_{1},\dots,x_{L})$ be $L$
independent samples from $u$. Independently, let $M\in\mathcal{M}$ be chosen
uniformly at random, and let
$X^{\prime}=(x^{\prime}_{1},\dots,x^{\prime}_{L})$ be $L$ independent samples
from $\pi_{M}$. Then $d_{\mathrm{TV}}\left(X,X^{\prime}\right)\leq 0.98$.

###### Proof.

(1) follows from Lemma 8 in [CDKS20]. (2) is proved in Section 8.3.2 in
[DDK19]. See also in Section 8.1 from [CDKS20] the same result for a slightly
different construction of $\pi_{M}$, where every edge is set to be
ferromagnetic with probability $1/2$ and antiferromagnetic otherwise. ∎

Define $H$ to be the random query history of length $2L$ with respect to
$\mathsf{Alg}$ and $\mathsf{Ora}[u]$, and let $\mathsf{output}$ denote the
random output with respect to $H$ and $\mathsf{Alg}$. Define $H^{\prime}$ to
be the random query history of length $2L$ generated by

  * •

Pick $M\in\mathcal{M}$ uniformly at random and let $\pi=\pi_{M}$;

  * •

Let $H^{\prime}$ be the random query history of length $2L$ with respect to
$\mathsf{Alg}$ and $\mathsf{Ora}[\pi]$.

Further, let $\mathsf{output}^{\prime}$ denote the random output with respect
to $H^{\prime}$ and $\mathsf{Alg}$. Then we can show the following key lemma.

######  Lemma 6.8.

For query histories $H,H^{\prime}$ of length $2L$ where $L\leq cn/\varepsilon$
and $\mathsf{output},\mathsf{output}^{\prime}$ defined as above, we have

$d_{\mathrm{TV}}\left(\mathsf{output},\mathsf{output}^{\prime}\right)\leq
d_{\mathrm{TV}}\left(H,H^{\prime}\right)\leq 0.99.$

###### Proof.

The first inequality follows from the data processing inequality. We focus on
the second one. For $M\in\mathcal{M}$ and $t\in\\{0,1\\}$, let $\pi_{M,t}$
denote the Ising model on $G=([n],M)$ with edge coupling
$t\beta=t\rho\varepsilon/\sqrt{n}$. Observe that $\pi_{M,0}=u$ and
$\pi_{M,1}=\pi_{M}$. We rewrite the process for generating the query histories
$H$ and $H^{\prime}$ of length $2L$ in the following equivalent form:

  * •

Let $M\in\mathcal{M}$ be chosen uniformly at random from $\mathcal{M}$;

  * •

Let $X_{t}=(x_{1},\dots,x_{L})\in\mathcal{X}_{n}^{L}$ be $L$ independent
samples from $\pi_{M,t}$;

  * •

Let $R_{t}=(r_{1},\dots,r_{L})\in\\{0,1\\}^{L}$ be $L$ independent Bernoulli
random variables with mean $(1+\tanh(t\rho\varepsilon/\sqrt{n}))/2$;

  * •

For $i=1,\dots,L$:

    * –

$\mathsf{Alg}$ receives
$\left((\tau_{1},a_{1}),\dots,(\tau_{i-1},a_{i-1})\right)$ as input and
generates $\tau_{i}\in\mathcal{T}$ (randomly) as output;

    * –

$\mathsf{Ora}[\pi]$ receives $\tau_{i}$ as input, which fixes all coordinates
but one say $j$, and suppose $j^{\prime}$ is matched to $j$ in $M$; then
$\mathsf{Ora}[\pi]$ outputs $a_{i}=(\tau_{i})_{j^{\prime}}$ (the
$j^{\prime}$-th coordinate of $\tau_{i}$) as the sampled value at the $j$-th
coordinate if $r_{i}=1$, and outputs $a_{i}=1-(\tau_{i})_{j^{\prime}}$
otherwise;

  * •

The query history is
$H_{t}=\left(x_{1},\dots,x_{L};(\tau_{1},a_{1}),\dots,(\tau_{L},a_{L})\right)$.

Observe that if $t=0$, then the final query history $H_{0}$ is distributed as
$H$; meanwhile, if $t=1$, then it is distributed as $H^{\prime}$. Moreover,
the process above can be viewed as a random mapping from the vector
$(M,X_{t},R_{t})$ to the query history $H_{t}$ where, for fixed
$(M,X_{t},R_{t})$, the randomness purely comes from the decision-making of
$\mathsf{Alg}$. Therefore, we can apply the data processing inequality and
obtain

$d_{\mathrm{TV}}\left(H,H^{\prime}\right)\leq
d_{\mathrm{TV}}\left((M,X_{0},R_{0}),(M,X_{1},R_{1})\right)\leq
d_{\mathrm{TV}}\left(X_{0},X_{1}\right)+d_{\mathrm{TV}}\left(R_{0},R_{1}\right).$

Note that $d_{\mathrm{TV}}\left(X_{0},X_{1}\right)\leq 0.98$ by Claim 6.7. For
the second term, we have

$d_{\mathrm{TV}}\left(R_{0},R_{1}\right)=d_{\mathrm{TV}}\left(\mathrm{Bin}\left(L,\frac{1}{2}\right),\mathrm{Bin}\left(L,\frac{1}{2}\left(1+\tanh\frac{\rho\varepsilon}{\sqrt{n}}\right)\right)\right)\leq
c^{\prime}\cdot\sqrt{L}\cdot\frac{\rho\varepsilon}{\sqrt{n}}\leq 0.01,$

where $c^{\prime}>0$ is a universal large constant, and $L\leq
cn/\varepsilon^{2}$ for $c$ sufficiently small. Therefore, we deduce that
$d_{\mathrm{TV}}\left(H,H^{\prime}\right)\leq 0.98+0.01=0.99$ as claimed. ∎

We end this section with the proof of Theorem 6.6.

###### Proof of Theorem 6.6.

Suppose for sake of contradiction that $\mathsf{Alg}$ satisfies both
properties as in Theorem 6.6. Then by a standard amplification technique for
failure probability, one can decrease the failure probability from $1/3$ to
$0.001$ with the number of samples needed increases only by a constant factor
(see [Can22, Lemma 1.1.1]). In particular, for query histories $H,H^{\prime}$
of length $2L$ where $L\leq cn/\varepsilon$ and
$\mathsf{output},\mathsf{output}^{\prime}$ defined as above, we have

$\Pr\nolimits\left(\mathsf{output}=\mathsf{Yes}\right)\geq
0.999\quad\text{and}\quad\Pr\nolimits\left(\mathsf{output}^{\prime}=\mathsf{Yes}\right)\leq
0.001.$

This implies
$d_{\mathrm{TV}}\left(\mathsf{output},\mathsf{output}^{\prime}\right)\geq
0.998$ which contradicts Lemma 6.8. ∎

##  7 Identity Testing with $\mathsf{Subcube\ Oracle}$

In this section we give our algorithmic results for identity testing with
access to the $\mathsf{Subcube\ Oracle}$.

###  7.1 Identity testing with exact conditional marginal distributions

Recall that $[i]=\\{1,\dots,i\\}$ for an integer $i\in\mathbb{N}^{+}$. The
following factorization of entropy is well-known, see e.g. [Ces01, MSW03,
CP21].

######  Lemma 7.1.

For any nonnegative function $f:\mathcal{K}^{n}\to\mathbb{R}_{\geq 0}$ we have

$\mathrm{Ent}f=\sum_{i=1}^{n}\mu\left[\mathrm{Ent}_{[n]\setminus[i-1]}\left(\mu_{[n]\setminus[i]}f\right)\right].$
(19)

Equivalently, for any distribution $\pi$ over $\mathcal{K}^{n}$ such that
$\pi\ll\mu$ we have

$D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)=\sum_{i=1}^{n}\mathbb{E}_{x\sim\pi_{[i-1]}}\left[D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid x)\right)\right].$ (20)

The functional form, Eq. 19, is equivalent to the probabilistic form, Eq. 20,
by taking $f=\pi/\mu$ to be the relative density.

We now give our testing algorithm with $\mathsf{Subcube\ Oracle}$.

######  Theorem 7.2.

Let $k=k(n)$ be an integer and let $b=b(n)\in(0,1/2]$ be a real. Suppose that
$\log\log(1/b)=O(\log n)$. There is an identity testing algorithm for all
$b$-marginally bounded distributions with query access to $\mathsf{Subcube\
Oracle}$ and for KL divergence with distance parameter $\varepsilon>0$. The
query complexity of the identity testing algorithm is

$O\left(\min\left\\{\frac{1}{\sqrt{b}}\cdot\frac{n}{\varepsilon}\log^{3}\left(\frac{n}{\varepsilon}\right),\,\sqrt{k}\log\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n^{2}}{\varepsilon^{2}}\log^{2}\left(\frac{n}{\varepsilon}\right)\right\\}\right).$

The running time of the algorithm is polynomial in all parameters and also
proportional to the time of computing the conditional marginal distributions
$\mu_{i}(\cdot\mid x)$ for any $i\in[n]$ and any feasible
$x\in\mathcal{K}^{[i-1]}$. Furthermore, if $k=2$, i.e., we have a binary
domain $\mathcal{K}=\\{0,1\\}$, the query complexity can be improved to

$O\left(\log\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n}{\varepsilon}\log^{3}\left(\frac{n}{\varepsilon}\right)\right).$

###### Proof.

We observe that Eq. 20 can be equivalently written as

$D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)=n\;\mathbb{E}_{(i,x)}\left[D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid x)\right)\right],$

where $i\in[n]$ is a uniformly random coordinate and $x$ is generated from
$\pi_{[i-1]}$. Therefore, Algorithm 1 still works once we generate the pair
$(i,x)$ in Line 1 from the correct distribution as just described, and define
$p^{x}_{i}=\pi_{i}(\cdot\mid x)$, $q^{x}_{i}=\mu_{i}(\cdot\mid x)$
correspondingly. The analysis is exactly the same with the constant $C$ for
approximate tensorization replaced by $1$. We omit the proofs here and only
highlight the differences: the coordinate balance $\eta$ is now replaced by
the marginal boundedness $b$, and the running time depends on the time to
compute the conditional marginal distributions $\mu_{i}(\cdot\mid x)$ for any
$i\in[n]$ and any $x\in\mathcal{K}^{[i-1]}$ such that $\mu_{[i-1]}(x)>0$. ∎

######  Remark 7.3.

We remark that the assumption of marginal boundedness can be relaxed to the
following slightly weaker version: for a fixed ordering of the coordinates,
for every $i\in[n]$, every $x\in\mathcal{K}^{[i-1]}$ with $\mu_{[i-1]}(x)>0$,
and every $a\in\mathcal{K}$, one has

$\text{either~{}~{}}\mu_{i}(a\mid x)=0,\quad\text{or~{}~{}}\mu_{i}(a\mid
x)\geq b.$

In some circumstances, this weaker notion of marginal boundedness can give a
better bound on the sample complexity.

Theorem 7.2 indicates that identity testing can be done efficiently for a wide
variety of families of distributions with the power of $\mathsf{Subcube\
Oracle}$, assuming that one can efficiently compute the exact marginal
probabilities under any conditioning. Below we give a few examples where
Theorem 7.2 applies. Instead of going into detailed definitions and technical
lemmas, we only describe the models without specifications to illustrate the
usage of Theorem 7.2.

  * •

Consider any undirected graphical model (e.g., Ising model, Potts model)
defined on trees of constant degrees. Then the distributions are
$\Omega(1)$-marginally bounded, and one can efficiently compute the marginal
probabilities under any pinning via, e.g., Belief Propagation. Hence, there is
a polynomial-time identity testing algorithm for undirected graphical models
on bounded-degree trees with $\mathsf{Subcube\ Oracle}$ access. The sample
complexity is $O((n/\varepsilon)\log^{3}(n/\varepsilon))$ where $n$ is the
number of vertices. If the degree is unbounded, then the marginal bound $b$
can be as small as $e^{-\Theta(n)}$. Still, by the second bound in Theorem 7.2
the number of samples needed is at most
$O((n^{3}/\varepsilon^{2})\log^{2}(n/\varepsilon))$.

  * •

Consider the Bayesian network on DAGs, and assume without loss of generality
that $[n]=\\{1,\dots,n\\}$ is the topological ordering of the DAG. In
particular, all conditional marginal probabilities at any coordinate $i\in[n]$
and conditioned on any feasible pinning $x\in\mathcal{K}^{[i-1]}$ are given by
the Bayesian network. If these conditional marginal probabilities are lower
bounded by $b=\Omega(1)$, then there is a polynomial-time identity testing
algorithm for such Bayesian networks with $\mathsf{Subcube\ Oracle}$ access,
and the sample complexity is $O((n/\varepsilon)\log^{3}(n/\varepsilon))$. If
$b$ is exponentially small, then similarly as before the sample complexity is
$O((n^{3}/\varepsilon^{2})\log^{2}(n/\varepsilon))$. See also Remark 7.3 above
on relaxing the marginal boundedness condition to specifically the topological
ordering.

  * •

Consider mixtures of polynomially many product distributions, each of which
has $\eta(\mu)=\Omega(1)$ as defined in Section 4.4.1. One can efficiently
compute the conditional marginal probabilities by the simple nature of
mixtures of product distributions. Then by Theorem 7.2, we have an efficient
identity testing algorithm with $\mathsf{Subcube\ Oracle}$ access and the
sample complexity is $O((n/\varepsilon)\log^{3}(n/\varepsilon))$. Similarly as
before, the sample complexity becomes
$O((n^{3}/\varepsilon^{2})\log^{2}(n/\varepsilon))$ when the minimum
$\eta(\mu)$ is exponentially small.

###  7.2 Identity testing with approximate conditional marginal distributions

In Theorem 7.2 we assume that one can compute exactly any conditional marginal
distribution in polynomial time. In some applications the exact computation is
not possible and one can get, at the best, an estimator of the conditional
marginal probabilities. As we will show in this subsection, identity testing
can still be done efficiently in this setting.

We first need a more robust version of Lemmas 4.3 and 4.9. We say there is an
FPRAS for a distribution $q$ over $\mathcal{K}$ if for any $\varepsilon>0$ and
$\delta\in(0,1)$, one can compute a distribution $\hat{q}$ over $\mathcal{K}$
as an approximation of $q$ such that, with probability $1-\delta$, we have
that for every $a\in\mathcal{K}$,

$e^{-\varepsilon}\leq\frac{\hat{q}(a)}{q(a)}\leq e^{\varepsilon},$

and $\hat{q}$ can be computed with running time polynomial in $k$,
$1/\varepsilon$, $\log(1/\delta)$, and the input size of $q$ (e.g., the number
of parameters representing $q$). We remark that if $q(a)=0$ then
$\hat{q}(a)=0$.

######  Lemma 7.4.

Let $k\in\mathbb{N}^{+}$ be an integer, and let $\varepsilon>0$, $b\in(0,1/2]$
be reals. Given an FPRAS for a target distribution $q$ over domain
$\mathcal{K}$ of size $k$ such that either $q(a)=0$ or $q(a)\geq b$ for any
$a\in\mathcal{K}$, and given sample access to an unknown distribution $p\ll q$
over $\mathcal{K}$, there exists a polynomial-time identity testing algorithm
that distinguishes with probability at least $2/3$ between the two cases

$p=q\quad\text{and}\quad D_{\mathrm{KL}}\left(p\,\|\,q\right)\geq\varepsilon.$
(21)

For $k\geq 3$, the sample complexity of the identity testing algorithm is

$O\left(\min\left\\{\frac{1}{\varepsilon\sqrt{b}},\,\frac{\sqrt{k}\ln(1/b)}{\varepsilon^{2}}\right\\}\right).$

For $k=2$, the sample complexity of the identity testing algorithm is

$O\left(\frac{\ln(1/b)}{\varepsilon}\right).$

###### Proof.

Let $m$ be an upper bound for the number of samples required in Lemmas 4.3 and
4.9, with the assumption being either $q(a)=0$ or $q(a)\geq b/2$ for any
$a\in\mathcal{K}$, distance parameter $\varepsilon/2$, and failure probability
$1/10$. Let $\xi=O(\min\\{\varepsilon,1/m\\})$ be a small constant, and let
$\hat{q}$ be an approximation of $q$ such that with probability $9/10$ we have
$e^{-\xi}\leq\hat{q}(a)/q(a)\leq e^{\xi}$ for every $a\in\mathcal{K}$. Notice
that if this holds then

$\left|D_{\mathrm{KL}}\left(p\,\|\,\hat{q}\right)-D_{\mathrm{KL}}\left(p\,\|\,q\right)\right|\leq\sum_{a\in\mathcal{K}}p(a)\left|\ln\left(\frac{q}{\hat{q}}\right)\right|\leq\xi.$

We then apply the identity testing algorithm $\mathcal{A}_{\textsc{kl-id}}$
from Lemmas 4.3 and 4.9 to the distributions $p,\hat{q}$ with distance
parameter $\varepsilon/2$ and failure probability $1/10$, and returns the
output of $\mathcal{A}_{\textsc{kl-id}}$ as our output. Note that
$\hat{q}(a)=0$ if $q(a)=0$ and $\hat{q}(a)\geq e^{-\xi}q(a)\geq b/2$ if
$q(a)\geq b$, assuming $\hat{q}$ is a $\xi$-approximation of $q$. Thus, the
number of samples required by $\mathcal{A}_{\textsc{kl-id}}$ is at most $m$.
If $D_{\mathrm{KL}}\left(p\,\|\,q\right)\geq\varepsilon$, then

$D_{\mathrm{KL}}\left(p\,\|\,\hat{q}\right)\geq
D_{\mathrm{KL}}\left(p\,\|\,q\right)-\left|D_{\mathrm{KL}}\left(p\,\|\,\hat{q}\right)-D_{\mathrm{KL}}\left(p\,\|\,q\right)\right|\geq\varepsilon-\xi\geq\frac{\varepsilon}{2}.$

Hence, the testing algorithm wrongly outputs Yes only if at least one of the
following happens

  1. (1)

$\hat{q}$ is not a $\xi$-approximation of $q$, which happens with probability
at most $1/10$;

  2. (2)

$\mathcal{A}_{\textsc{kl-id}}$ makes a mistake, which happens with probability
at most $1/10$.

This shows that the failure probability is at most $1/5$. If $p=q$, then
notice that

$d_{\mathrm{TV}}\left(p,\hat{q}\right)=d_{\mathrm{TV}}\left(q,\hat{q}\right)=O(\xi)\leq\frac{1}{10m}.$

We consider an optimal coupling between $m$ independent samples from $p$ and
$m$ independent samples from $\hat{q}$, so the probability that these two sets
of $m$ samples are not exactly the same is at most $1/10$. One can think of
the testing process as follows: we try to send $m$ samples from $\hat{q}$ to
$\mathcal{A}_{\textsc{kl-id}}$, and it succeeds only when the samples are
coupled with those from $p$. Therefore, the failure probability, in addition
to (1) and (2) above, also includes this uncoupled probability, and hence is
at most $3/10$. Finally, the number of samples needed, $m$, is bounded in
Lemmas 4.3 and 4.9. ∎

Lemma 7.4, combined with the proof of Theorem 7.2, immediately implies the
following theorem. See also Remark 7.3 for the discussion on relaxing marginal
boundedness.

######  Theorem 7.5.

Let $k=k(n)$ be an integer and let $b=b(n)\in(0,1/2]$ be a real. Suppose that
$\log\log(1/b)=O(\log n)$. There is an identity testing algorithm for all
$b$-marginally bounded distributions with query access to $\mathsf{Subcube\
Oracle}$ and for KL divergence with distance parameter $\varepsilon>0$. The
query complexity of the identity testing algorithm is

$O\left(\min\left\\{\frac{1}{\sqrt{b}}\cdot\frac{n}{\varepsilon}\log^{3}\left(\frac{n}{\varepsilon}\right),\,\sqrt{k}\log\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n^{2}}{\varepsilon^{2}}\log^{2}\left(\frac{n}{\varepsilon}\right)\right\\}\right).$

The running time of the algorithm is polynomial in all parameters assuming
that there is an FPRAS for the conditional marginal distributions
$\mu_{i}(\cdot\mid x)$ for any $i\in[n]$ and any feasible
$x\in\mathcal{K}^{[i-1]}$. Furthermore, if $k=2$, i.e., we have a binary
domain $\mathcal{K}=\\{0,1\\}$, the query complexity can be improved to

$O\left(\log\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n}{\varepsilon}\log^{3}\left(\frac{n}{\varepsilon}\right)\right).$

Again, we give a few examples as applications of Theorem 7.5, omitting all the
technical details.

  * •

Consider the Ising model with the interaction matrix $J$ (with entries being
$\beta_{uv}$’s and assumed to be positive semidefinite). We know from recent
works [EKZ22, AJK+22, KLR22] that one can efficiently estimate all conditional
marginal probabilities when $\left\lVert J\right\rVert_{2}<1$ under any
external fields. There are two special features for this application. The
first is that the marginal bounds could potentially be as small as
$e^{-\Theta(\sqrt{n})}$. The second is that we can only approximate the
conditional marginal probabilities rather than get the exact values, and hence
we should apply Theorem 7.5 instead of Theorem 7.2. With access to the
$\mathsf{Subcube\ Oracle}$, one can obtain a polynomial-time identity testing
algorithm for this family of Ising models with sample complexity
$O((n^{3/2}/\varepsilon)\log^{3}(n/\varepsilon))$ (note that $k=2$).

  * •

Consider the monomer-dimer model (weighted matchings) on arbitrary (unbounded-
degree) graphs. We know from the classical work [JS89] that one can
approximate the conditional marginal distributions for all pinnings. Similar
to the previous example, the marginal probabilities can be exponentially small
(in the number of vertices) and one can at the best approximate them
efficiently rather than computing them exactly. Still, we can apply Theorem
7.5 to obtain an efficient identity testing algorithm with access to the
$\mathsf{Subcube\ Oracle}$ with sample complexity
$O((mn/\varepsilon)\log^{3}(n/\varepsilon))$ where $m$ is the number of edges
of the graph (which is the dimension) and $n$ is the number of vertices (note
that $k=2$).

###  7.3 Estimating KL divergence with additive error

With access to the $\mathsf{Subcube\ Oracle}$, we can also estimate the KL
divergence from an unknown distribution $\pi$ to a given distribution $\mu$
within an arbitrary additive error in polynomial time. This corresponds to the
_tolerant identity testing_ problem for KL divergence; that is, given
$s,\varepsilon>0$, we want to distinguish between
$D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)\leq s$ and
$D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)\geq s+\varepsilon$.

We first consider estimating KL divergence for distributions on a finite
domain of size $k$.

######  Lemma 7.6.

Let $k\in\mathbb{N}^{+}$ be an integer, and let $\varepsilon>0$, $b\in(0,1/2]$
be reals. Given an FPRAS for a target distribution $q$ over domain
$\mathcal{K}$ of size $k$ such that either $q(a)=0$ or $q(a)\geq b$ for any
$a\in\mathcal{K}$, and given sample access to an unknown distribution $p\ll q$
over $\mathcal{K}$, there exists a polynomial-time algorithm that computes
$\widehat{R}$ such that with probability at least $2/3$ it holds

$\left|\widehat{R}-D_{\mathrm{KL}}\left(p\,\|\,q\right)\right|\leq\varepsilon,$
(22)

with sample complexity

$O\left(\frac{k}{\varepsilon\log(k/\varepsilon)}+\frac{\log^{2}(1/b)}{\varepsilon^{2}}\right).$

For a distribution $p$ over a finite domain $\mathcal{K}$, the (Shannon)
entropy of $p$ is defined as

$H(p)=\sum_{a\in\mathcal{K}}p(a)\ln\left(\frac{1}{p(a)}\right).$

Observe that if $p\ll q$ are two distributions over $\mathcal{K}$, then

$D_{\mathrm{KL}}\left(p\,\|\,q\right)=\sum_{a\in\mathcal{K}}p(a)\ln\left(\frac{1}{q(a)}\right)-\sum_{a\in\mathcal{K}}p(a)\ln\left(\frac{1}{p(a)}\right)=\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]-H(p).$ (23)

It suffices to estimate the two terms on the right-hand side of Eq. 23
respectively with good enough accuracy.

We need the following well-known result from [VV17b] for estimating the
entropy of an unknown distribution from samples, see also [VV11, JVHW15,
WY16].

######  Lemma 7.7 ([VV17b]).

Let $k\in\mathbb{N}^{+}$ be an integer, and let $\varepsilon>0$ be a real.
Given sample access to an unknown distribution $p$ over domain $\mathcal{K}$
of size $k$, there exists a polynomial-time algorithm that computes
$\widehat{H}$ such that with probability at least $9/10$ it holds

$\left|\widehat{H}-H(p)\right|\leq\varepsilon,$ (24)

with sample complexity

$O\left(\frac{k}{\varepsilon\log(k/\varepsilon)}+\frac{\log^{2}k}{\varepsilon^{2}}\right).$

For the fist term in Eq. 23, we show the following estimator.

######  Lemma 7.8.

Let $k\in\mathbb{N}^{+}$ be an integer, and let $\varepsilon>0$, $b\in(0,1/2]$
be reals. Given an FPRAS for a target distribution $q$ over domain
$\mathcal{K}$ of size $k$ such that either $q(a)=0$ or $q(a)\geq b$ for any
$a\in\mathcal{K}$, and given sample access to an unknown distribution $p\ll q$
over $\mathcal{K}$, there exists a polynomial-time algorithm that computes
$\widehat{G}$ such that with probability at least $4/5$ it holds

$\left|\widehat{G}-\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]\right|\leq\varepsilon,$ (25)

with sample complexity

$O\left(\frac{\ln^{2}(1/b)}{\varepsilon^{2}}\right).$

###### Proof.

Compute an approximation $\hat{q}$ of $q$ such that, with probability $9/10$,
we have that $e^{-\varepsilon/2}\leq\hat{q}(a)/q(a)\leq e^{\varepsilon/2}$ for
every $a\in\mathcal{K}$ with $q(a)>0$, and $\hat{q}(a)=0$ for $q(a)=0$.
Generate $m$ independent samples from $p$, denoted by $a_{1},\dots,a_{m}$.
Then our estimator is defined as

$\widehat{G}=\frac{1}{m}\sum_{j=1}^{m}\ln\left(\frac{1}{\hat{q}(a_{j})}\right).$

We will show that $\widehat{G}$ satisfies Eq. 25 with probability at least
$4/5$ for

$m=\left\lceil\frac{8\ln^{2}(1/b)}{\varepsilon^{2}}\right\rceil.$

Observe that

$\displaystyle\left|\widehat{G}-\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]\right|$ $\displaystyle\leq{}$
$\displaystyle\left|\frac{1}{m}\sum_{j=1}^{m}\ln\left(\frac{1}{\hat{q}(a_{j})}\right)-\frac{1}{m}\sum_{j=1}^{m}\ln\left(\frac{1}{q(a_{j})}\right)\right|+\left|\frac{1}{m}\sum_{j=1}^{m}\ln\left(\frac{1}{q(a_{j})}\right)-\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]\right|$ (26)

Assuming $\hat{q}$ is an $(\varepsilon/2)$-approximation of $q$, we can upper
bound the first term in Eq. 26 by

$\frac{1}{m}\sum_{j=1}^{m}\left|\ln\left(\frac{\hat{q}(a_{j})}{q(a_{j})}\right)\right|\leq\frac{1}{m}\sum_{j=1}^{m}\frac{\varepsilon}{2}=\frac{\varepsilon}{2}.$

Meanwhile, for the second term in Eq. 26, since $0\leq\ln(1/q(a))\leq\ln(1/b)$
for all $a\in\mathcal{K}$ with $q(a)>0$ and since $p\ll q$, we deduce from
Hoeffding’s inequality that

$\displaystyle\Pr\left(\left|\frac{1}{m}\sum_{j=1}^{m}\ln\left(\frac{1}{q(a_{j})}\right)-\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]\right|\geq\frac{\varepsilon}{2}\right)\leq
2\exp\left(-\frac{\varepsilon^{2}m}{2\ln^{2}(1/b)}\right)\leq\frac{1}{10},$

provided $m\geq(8/\varepsilon^{2})\ln^{2}(1/b).$ Therefore, we deduce from Eq.
26 that

$\left|\widehat{G}-\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]\right|\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon$

with failure probability at most $1/10+1/10=1/5$ by the union bound, as
wanted. ∎

Lemma 7.6 then follows easily from Lemmas 7.7 and 7.8.

###### Proof Lemma 7.6.

Since the sample complexity upper bound we want to show is monotone increasing
in $k$, we can safely assume without loss of generality that $q$ is fully
supported on $\mathcal{K}$, i.e., $q(a)\geq b$ for each $a\in\mathcal{K}$. In
particular, this implies that $b\leq 1/k$. Take $\widehat{G}$ from Lemma 7.8
and $\widehat{H}$ from Lemma 7.7, and let
$\widehat{R}=\widehat{G}-\widehat{H}$. We then deduce from Eq. 23 that

$\left|\widehat{R}-D_{\mathrm{KL}}\left(p\,\|\,q\right)\right|\leq\left|\widehat{G}-\mathbb{E}_{a\sim
p}\left[\ln\left(\frac{1}{q(a)}\right)\right]\right|+\left|\widehat{H}-H(p)\right|\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon,$

which fails with probability at most $1/5+1/10=3/10$ by the union bound. The
running time is polynomial in all parameters and depends on the given FPRAS
for $q$. The sample complexity is given by

$O\left(\frac{k}{\varepsilon\log(k/\varepsilon)}+\frac{\log^{2}k}{\varepsilon^{2}}\right)+O\left(\frac{\ln^{2}(1/b)}{\varepsilon^{2}}\right)=O\left(\frac{k}{\varepsilon\log(k/\varepsilon)}+\frac{\log^{2}(1/b)}{\varepsilon^{2}}\right),$

since we have $k\leq 1/b$. ∎

We now give our main theorem for estimating KL divergence with
$\mathsf{Subcube\ Oracle}$ access.

######  Theorem 7.9.

Let $k=k(n)$ be an integer and let $b=b(n)\in(0,1/2]$ be a real. Suppose that
$k=O(n)$ and $\log\log(1/b)=O(\log n)$. Given a visible distribution $\mu$
over $\mathcal{K}^{n}$ that is $b$-marginally bounded, and given access to
$\mathsf{Subcube\ Oracle}$ for a hidden distribution $\pi\ll\mu$ over
$\mathcal{K}^{n}$, there is an algorithm that for any $\varepsilon>0$ computes
$\widehat{S}$ such that with probability at least $2/3$ it holds

$\left|\widehat{S}-D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)\right|\leq\varepsilon.$
(27)

The query complexity of the algorithm is

$O\left(\log^{4}\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n^{4}}{\varepsilon^{4}}\log\left(\frac{n}{\varepsilon}\right)\right).$

The running time of the algorithm is polynomial in all parameters assuming
that there is an FPRAS for the conditional marginal distributions
$\mu_{i}(\cdot\mid x)$ for any $i\in[n]$ and any feasible
$x\in\mathcal{K}^{[i-1]}$.

###### Proof.

From Eq. 20 we observe that

$D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)=n\;\mathbb{E}_{(i,x)}\left[D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid x)\right)\right],$

where $(i,x)$ is a random pair generated by taking a uniformly random
coordinate $i\in[n]$ and sampling $x\in\mathcal{K}^{[i-1]}$ from the marginal
of $\pi$ on the first $i-1$ coordinates. Hence, it suffices to estimate
$\mathbb{E}_{(i,x)}\left[D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid x)\right)\right]$ with additive error
$\varepsilon/n$.

Let $(i_{1},x_{1}),\dots,(i_{L},x_{L})$ be $L$ independent random pairs
generated via the $\mathsf{General\ Oracle}$ (which is contained in the power
of $\mathsf{Subcube\ Oracle}$), where we define

$L=\left\lceil\frac{8n^{2}\ln^{2}(1/b)}{\varepsilon^{2}}\right\rceil.$

For $1\leq\ell\leq L$, we let

$R_{\ell}=D_{\mathrm{KL}}\left(\pi_{i_{\ell}}(\cdot\mid
x_{\ell})\,\|\,\mu_{i_{\ell}}(\cdot\mid x_{\ell})\right).$

Furthermore, for each $\ell$ let $\widehat{R}_{\ell}$ be an estimate of
$R_{\ell}$ which is obtained from Lemma 7.6 using the $\mathsf{Subcube\
Oracle}$, such that

$\Pr\left(\left|\widehat{R}_{\ell}-R_{\ell}\right|\geq\frac{\varepsilon}{2n}\right)\leq\frac{1}{10L}.$

Then, by the union bound we have

$\Pr\left(\left|\frac{1}{L}\sum_{\ell=1}^{L}\widehat{R}_{\ell}-\frac{1}{L}\sum_{\ell=1}^{L}R_{\ell}\right|\geq\frac{\varepsilon}{2n}\right)\leq\sum_{\ell=1}^{L}\Pr\left(\left|\widehat{R}_{\ell}-R_{\ell}\right|\geq\frac{\varepsilon}{2n}\right)\leq
L\cdot\frac{1}{10L}=\frac{1}{10}.$

Note that using the standard amplification technique for the failure
probability, the number of samples we need for each $\ell$ is

$O\left(\frac{kn}{\varepsilon\log(kn/\varepsilon)}+\frac{n^{2}\log^{2}(1/b)}{\varepsilon^{2}}\right)\cdot
O\left(\log
L\right)=O\left(\log^{2}\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n^{2}}{\varepsilon^{2}}\log\left(\frac{n}{\varepsilon}\right)\right),$

where we use the assumptions $k=O(n)$ and $\log\log(1/b)=O(\log n)$.

Meanwhile, we observe $0\leq D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid x)\right)\leq\ln(1/b)$ for any feasible pair $(i,x)$
since $\mu$ is $b$-marginally bounded and $\pi\ll\mu$. Hence, Hoeffding’s
inequality implies that

$\Pr\left(\left|\frac{1}{L}\sum_{\ell=1}^{L}R_{\ell}-\mathbb{E}_{(i,x)}\left[D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid
x)\right)\right]\right|\geq\frac{\varepsilon}{2n}\right)\leq
2\exp\left(-\frac{\varepsilon^{2}L}{2n^{2}\ln^{2}(1/b)}\right)\leq\frac{1}{10},$

provided $L\geq(8n^{2}/\varepsilon^{2})\ln^{2}(1/b).$

Therefore, by letting our estimator to be

$\widehat{S}=\frac{n}{L}\sum_{\ell=1}^{L}\widehat{R}_{\ell},$

we deduce that

$\displaystyle\left|\widehat{S}-D_{\mathrm{KL}}\left(\pi\,\|\,\mu\right)\right|$
$\displaystyle\leq
n\left|\frac{1}{L}\sum_{\ell=1}^{L}\widehat{R}_{\ell}-\frac{1}{L}\sum_{\ell=1}^{L}R_{\ell}\right|+n\left|\frac{1}{L}\sum_{\ell=1}^{L}R_{\ell}-\mathbb{E}_{(i,x)}\left[D_{\mathrm{KL}}\left(\pi_{i}(\cdot\mid
x)\,\|\,\mu_{i}(\cdot\mid x)\right)\right]\right|$ $\displaystyle\leq
n\cdot\frac{\varepsilon}{2n}+n\cdot\frac{\varepsilon}{2n}=\varepsilon,$

with failure probability at most $1/10+1/10=1/5$ by the union bound. Finally,
the query complexity is given by

$O\left(\log^{2}\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n^{2}}{\varepsilon^{2}}\log\left(\frac{n}{\varepsilon}\right)\right)\cdot
L=O\left(\log^{4}\Big{(}\frac{1}{b}\Big{)}\cdot\frac{n^{4}}{\varepsilon^{4}}\log\left(\frac{n}{\varepsilon}\right)\right),$

as claimed. ∎

We remark that Theorem 7.9 is applicable to all the examples mentioned in
Sections 7.2 and 7.1. See also Remark 7.3 on relaxing the marginal boundedness
condition.

##  8 Conclusion and Open Problems

In this paper we give efficient algorithms for identity testing with access to
$\mathsf{Coordinate\ Oracle}$ and $\mathsf{General\ Oracle}$, and also
establish matching computational hardness and information-theoretical lower
bounds. Our algorithmic result builds on the fact that the visible
distribution satisfies approximate tensorization of entropy. While we show
that for the antiferromagnetic Ising model, there is no polynomial-time
identity testing algorithm when approximate tensorization fails, it is in
general unclear if one can get a testing algorithm running in polynomial time
without approximate tensorization, using either $\mathsf{Coordinate\ Oracle}$
or $\mathsf{Subcube\ Oracle}$ in addition to $\mathsf{General\ Oracle}$. One
important example is the ferromagnetic Ising model at all temperatures. We
know that approximate tensorization fails at low temperature (large $\beta$)
since the Glauber dynamics has exponential mixing time. We do not know whether
an efficient identity testing algorithm exists or not even with access to the
more powerful $\mathsf{Subcube\ Oracle}$. Note that our Theorem 7.2 does not
apply to ferromagnetic Ising models since we cannot estimate conditional
marginal probabilities under an arbitrary pinning (corresponding to
ferromagnetic Ising models with inconsistent local fields). Another important
example is mixtures of product distributions. It is easy to show that
approximate tensorization could fail even for a mixture of two product
distributions with equal weights. We know from Theorem 7.2 that there is an
efficient identity testing algorithm for the family of mixtures of
polynomially many balanced product distributions given access to the
$\mathsf{Subcube\ Oracle}$. It is unclear to us, however, that if there is a
polynomial-time testing algorithm using only the weaker $\mathsf{Coordinate\
Oracle}$.

## References

  * [ADK15] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath.  Optimal testing for properties of distributions.  Advances in Neural Information Processing Systems, 28, 2015.
  * [AJK+22] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Entropic independence: Optimal mixing of down-up random walks.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), page 1418–1430, 2022.
  * [ALG20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1319–1330, 2020.
  * [BBC+19] Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda.  Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models.  In Proceedings of the 32nd Annual Conference on Computational Learning Theory (COLT), volume 99, pages 283–298, 2019.
  * [BC18] Rishiraj Bhattacharyya and Sourav Chakraborty.  Property testing of joint distributions using conditional samples.  ACM Trans. Comput. Theory, 10(4), 2018.  Article No. 16.
  * [BCC+22] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda.  On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization.  In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3670–3692, 2022.
  * [BCŠV20] Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda.  Hardness of identity testing for restricted Boltzmann machines and Potts models.  In Proceedings of the Conference on Learning Theory (COLT), pages 514–529, 2020.
  * [BCY22] Arnab Bhattacharyya, Clément L Canonne, and Joy Qiping Yang.  Independence testing for bounded degree Bayesian network.  arXiv preprint arXiv:2204.08690, 2022.
  * [BDH22] Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris.  Spectral gap in random bipartite biregular graphs and applications.  Combinatorics, Probability and Computing, 31(2):229–267, 2022.
  * [BFF+01] Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White.  Testing random variables for independence and identity.  In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 442–451, 2001.
  * [BG99] Sergej G Bobkov and Friedrich Götze.  Exponential integrability and transportation cost related to logarithmic Sobolev inequalities.  Journal of Functional Analysis, 163(1):1–28, 1999.
  * [BGKV21] Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, and NV Vinodchandran.  Testing product distributions: A closer look.  In Algorithmic Learning Theory (ALT), pages 367–396, 2021.
  * [Can22] Clément L. Canonne.  Topics and techniques in distribution testing: A biased but representative sample.  2022\.
  * [CCK+21] Clement L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten.  Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 321–336, 2021.
  * [CDKS20] Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart.  Testing bayesian networks.  IEEE Transactions on Information Theory, 66(5):3132–3170, 2020\.
  * [CDVV14] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1193–1203. SIAM, 2014.
  * [Ces01] Filippo Cesi.  Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields.  Probability Theory and Related Fields, 120:569–584, 2001.
  * [CFGM16] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah.  On the power of conditional samples in distribution testing.  SIAM Journal on Computing, 45(4):1261–1296, 2016.
  * [CGG+16] Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda.  #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region.  Journal of Computer and System Sciences, 82(5):690–711, 2016.
  * [CGŠV21] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Rapid mixing for colorings via spectral independence.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557, 2021.
  * [CJLW21] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten.  Learning and testing junta distributions with subcube conditioning.  In Proceedings of the 34th Conference on Learning Theory (COLT), volume 134, pages 1060–1113, 2021.
  * [CLV20] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Rapid mixing of Glauber dynamics up to uniqueness via contraction.  In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1307–1318, 2020.
  * [CLV21a] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1537–1550, 2021.
  * [CLV21b] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Spectral independence via stability and applications to Holant-type problems.  In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 149–160, 2021.
  * [CMT15] Pietro Caputo, Georg Menz, and Prasad Tetali.  Approximate tensorization of entropy at high temperature.  Annales de la Faculté des sciences de Toulouse: Mathématiques, Ser. 6, 24(4):691–716, 2015.
  * [CP21] Pietro Caputo and Daniel Parisi.  Block factorization of the relative entropy via spatial mixing.  Communications in Mathematical Physics, 388(2):793–818, 2021.
  * [CRS15] Clément L Canonne, Dana Ron, and Rocco A. Servedio.  Testing probability distributions using conditional samples.  SIAM Journal on Computing, 44(3):540–616, 2015.
  * [CS22] Clément L Canonne and Yucheng Sun.  Optimal closeness testing of discrete distributions made (complex) simple.  arXiv preprint arXiv:2204.12640, 2022.
  * [DDK19] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing Ising models.  IEEE Transactions on Information Theory, 65(11):6829–6852, 2019\.
  * [DGK+21] Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, John Peebles, and Eric Price.  Optimal testing of discrete distributions with high probability.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 542–555, 2021.
  * [DK16] Ilias Diakonikolas and Daniel M Kane.  A new approach for testing properties of discrete distributions.  In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 685–694, 2016.
  * [DKW18] Constantinos Daskalakis, Gautam Kamath, and John Wright.  Which distribution distances are sublinearly testable?  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2747–2764. SIAM, 2018.
  * [DP17] Constantinos Daskalakis and Qinxuan Pan.  Square Hellinger subadditivity for Bayesian networks and its applications to identity testing.  In Conference on Learning Theory (COLT), pages 697–703, 2017.
  * [EKZ22] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni.  A spectral condition for spectral gap: fast mixing in high-temperature Ising models.  Probability Theory and Related Fields, 182:1035–1051, 2022.
  * [FGYZ21] Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang.  Rapid mixing from spectral independence beyond the Boolean domain.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1558–1577, 2021.
  * [FJO+15] Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh.  Faster algorithms for testing under conditional sampling.  In Proceedings of The 28th Conference on Learning Theory (COLT), volume 40, pages 607–636, 2015.
  * [Fra12] Joel N Franklin.  Matrix theory.  Dover Publications, Inc., 2012.
  * [GK04] David Galvin and Jeff Kahn.  On phase transition in the hard-core model on ${Z}^{d}$.  Combinatorics, Probability and Computing, 13(2):137–164, 2004.
  * [Gol04] Oded Goldreich.  Foundations of cryptography. II: Basic applications.  Cambridge University Press, 2004.
  * [Gol16] Oded Goldreich.  The uniform distribution is complete with respect to testing identity to a fixed distribution.  In Electron. Colloquium Comput. Complex., volume 23, page 15, 2016\.
  * [GSS19] Friedrich Götze, Holger Sambale, and Arthur Sinulis.  Higher order concentration for functions of weakly dependent random variables.  Electronic Journal of Probability, 24:1–19, 2019.
  * [GŠV16] A. Galanis, D. Štefankovič, and E. Vigoda.  Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models.  Combinatorics, Probability and Computing, 25(4):500–559, 2016.
  * [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson.  Expander graphs and their applications.  Bulletin of the American Mathematical Society, 43(4):439–561, 2006\.
  * [JKP20] Matthew Jenssen, Peter Keevash, and Will Perkins.  Algorithms for #BIS-hard problems on expander graphs.  SIAM Journal on Computing, 49(4):681–710, 2020.
  * [JS89] Mark Jerrum and Alistair Sinclair.  Approximating the permanent.  SIAM Journal on Computing, 18(6):1149–1178, 1989.
  * [JVHW15] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman.  Minimax estimation of functionals of discrete distributions.  IEEE Transactions on Information Theory, 61(5):2835–2885, 2015\.
  * [KLR22] Frederic Koehler, Holden Lee, and Andrej Risteski.  Sampling approximately low-rank Ising models: MCMC meets variational methods.  In Proceedings of The 35th Conference on Learning Theory (COLT), 2022.
  * [KM17] Adam Klivans and Raghu Meka.  Learning graphical models using multiplicative weights.  In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 343–354, 2017.
  * [Liu21] Kuikui Liu.  From coupling to spectral independence and blackbox comparison with the down-up walk.  In APPROX-RANDOM, 2021.
  * [Mar19] Katalin Marton.  Logarithmic Sobolev inequalities in discrete product spaces.  Combinatorics, Probability and Computing, 28(6):919–935, 2019.
  * [MRRW97] Michael S. O. Molloy, Hanna Robalewska, Robert W. Robinson, and Nicholas C. Wormald.  1-factorizations of random regular graphs.  Random Structures & Algorithms, 10(3):305–321, 1997.
  * [MSW03] Fabio Martinelli, Alistair Sinclair, and Dror Weitz.  The Ising model on trees: Boundary conditions and mixing time.  In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 628–639. IEEE, 2003.
  * [MT06] Ravi Montenegro and Prasad Tetali.  Mathematical aspects of mixing times in Markov chains.  Foundations and Trends® in Theoretical Computer Science, 1(3):237–354, 2006.
  * [Nar21] Shyam Narayanan.  On tolerant distribution testing in the conditional sampling model.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 357–373, 2021.
  * [Pan08] Liam Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Transactions on Information Theory, 54(10):4750–4755, 2008\.
  * [PW96] James Gary Propp and David Bruce Wilson.  Exact sampling with coupled Markov chains and applications to statistical mechanics.  Random Structures & Algorithms, 9(1-2):223–252, 1996.
  * [Sly10] Allan Sly.  Computational transition at the uniqueness threshold.  In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 287–296, 2010.
  * [SS14] A. Sly and N. Sun.  Counting in two-spin models on $d$-regular graphs.  Ann. Probab., 42(6):2383–2416, 2014.
  * [VV11] Gregory Valiant and Paul Valiant.  The power of linear estimators.  In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 403–412. IEEE, 2011.
  * [VV17a] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  SIAM Journal on Computing, 46(1):429–455, 2017.
  * [VV17b] Gregory Valiant and Paul Valiant.  Estimating the unseen: Improved estimators for entropy and other properties.  Journal of the ACM (JACM), 64(6):1–41, 2017.
  * [WY16] Yihong Wu and Pengkun Yang.  Minimax rates of entropy estimation on large alphabets via best polynomial approximation.  IEEE Transactions on Information Theory, 62(6):3702–3720, 2016\.