involved random variable will be included in a ball and will not be used by
any other constructed augmenting event who triggers if condition next time.

Thus, it is sufficient to bound the probability that there exists a subset of
$k$ mutually independent events in $\mathcal{F}$ such that all of them happen
together, which is

$\sum_{\begin{subarray}{c}F\subseteq\mathcal{F},|F|=k,\\\ \text{the events in
$F$}\\\ \text{are independent}\end{subarray}}\prod_{f\in F}\Pr[\text{$f$
happens}]\leq\sum_{\begin{subarray}{c}F\subseteq\mathcal{F},|F|=k,\\\
\text{the events in $F$}\\\ \text{are independent}\end{subarray}}\prod_{f\in
F}\frac{1}{n^{3}}\leq n^{2k}\cdot\frac{1}{n^{3k}}=\frac{1}{n^{k}}.$

For any $0<\eta<1$, the probability that the if condition in Algorithm 1 is
triggered at least $k=\log_{n}\frac{1}{\eta}$ times is at most
$n^{-k}\leq\eta$. Note that each time the if condition is triggered, the value
of $\mathcal{D}$ will increase by $\ell$. Thus, with probability $1-\eta$, the
contribution $\mathcal{D}$ of this case is bounded by
$\widetilde{O}(|\bm{\mathcal{{R}}}|\cdot\log^{2}n\cdot\log^{2}\frac{1}{\gamma}\cdot\log\frac{1}{\eta})$.

Overall, for any $0<\eta<1$, we have
$\mathcal{D}=\widetilde{O}(|\bm{\mathcal{{R}}}|\cdot\log^{2}n\cdot\log^{2}\frac{1}{\gamma}\cdot\log\frac{1}{\eta})$
with probability $1-\eta$.

##  7 Analysis of Resampling

In this section, we analyze the _Resampling_ phase of the algorithm. The
correctness and efficiency of the _RecursiveSampling_ procedure (Items 1 and 2
in Lemma 3.11) are respectively proved in Sections 7.1 and 7.2. The accuracy
of the estimation (Lemma 3.10) in the augmented instance is proved in Section
7.3. The correctness of substituting (Lemma 3.12) is proved in Section 7.4.
Finally, the analysis of the _Resampling_ phase (Lemma 3.11) is wrapped up in
Section 7.5.

###  7.1 Correctness of _RecursiveSampling_ (Proof of Item 1 in Lemma 3.11)

First, we prove Item 1 of Lemma 3.11, which guarantees the correctness of
Algorithm 2.

Assume that 3.9 is satisfied by the input of _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$. Our goal is to show that
$\bm{{Y}}\sim\mu_{I}$ when the procedure returns. This is proved by a
structural induction. For the induction basis $\Lambda=V$, Algorithm 2 is
executed with probability $1$ and the resampled $\bm{{Y}}$ follows the
distribution $\mu_{I}$.

For the general case, assume that all recursive calls made within
_RecursiveSampling_ $(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$
return with the correct sampling results as long as 3.9 is satisfied by the
input arguments to these recursive calls. We then prove $\bm{{Y}}\sim\mu_{I}$
when _RecursiveSampling_ $(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$
returns.

In Algorithm 2, a $\rho\in[0,1)$ is drawn uniformly at random beforehand. Then
an estimation $[L,R]$ of the probability
$P=\Pr_{\bm{{X}}\sim\mu_{I}}[\,\bm{{X}}\text{ avoids }A_{\lambda}\,]$ is
dynamically improved based on local information, to determine whether $\rho<P$
(in which case Algorithm 2 is satisfied, and the algorithm enters the zone for
generating $\bm{{Y}}\sim\mu_{\hat{I}}$) or $\rho\geq P$ (in which case
Algorithm 2 is satisfied, and the algorithm enters the zone for generating
$\bm{{Y}}\sim\mu_{\hat{I}^{\prime}}$). This inspires us to define the
following events:

$\displaystyle\mathcal{F}_{1}:\quad\text{\lx@cref{creftypecap~refnum}{line:first-
if} is satisfied, and the algorithm enters the zone for generating
$\bm{{Y}}\sim\mu_{\hat{I}}$}$
$\displaystyle\overline{\mathcal{F}_{1}}:\quad\text{\lx@cref{creftypecap~refnum}{line:second-
if} is satisfied, and the algorithm enters the zone for generating
$\bm{{Y}}\sim\mu_{\hat{I}^{\prime}}$.}$

Once the algorithm enters one of these two zones, it will not leave the zone
until the algorithm returns. Thus, the above two events are mutually
exclusive. Furthermore, at least one of them must occur eventually. Indeed,
for $P\triangleq\Pr_{\bm{{X}}\sim\mu_{I}}\left[\,\bm{{X}}\text{ avoids
}A_{\lambda}\,\right]$, we have the following claim.

######  Claim 7.1.

$\Pr[\mathcal{F}_{1}]=P$ and $\Pr[\overline{\mathcal{F}_{1}}]=1-P$.

###### Proof.

Let $\ell_{0}=\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})$. By Lemma 3.1,
$A_{\lambda}$ is defined on the random variables in
$\mathsf{vbl}(B_{\ell_{0}}(\Lambda))$. For $i\geq 1$, let
$\ell_{i}\triangleq\ell_{0}\left(\zeta_{0}^{i},\alpha_{1},\alpha_{2}\cdot\zeta_{0}^{i}\right)$.
For $i\geq 1$, let

$\displaystyle\mathfrak{{J}}_{i}\triangleq\\{J=(\\{X_{i}\\}_{i\in
U_{J}},\\{A_{v}\\}_{v\in V_{J}})~{}\mid{}$ $J$ is $\alpha$-satisfiable and
$J\left(V_{J}\setminus B^{D_{J}}_{\ell_{0}+\ell_{i}}(\Lambda)\right)$ is
$\gamma$-satisfiable $\displaystyle\text{and
}\left.J\left(B^{D_{J}}_{\ell_{0}+\ell_{i}+1}(\Lambda)\right)=I\left(B^{D_{I}}_{\ell_{0}+\ell_{i}+1}(\Lambda)\right)\right\\}.$

For $i\geq 1$, let

$L_{i}\triangleq\inf_{J\in\mathfrak{{J}}_{i}}\Pr_{\bm{{X}}\sim\mu_{J}}[\text{
$\bm{{X}}$ avoids $A_{\bar{\lambda}}$ }]\quad\text{ and }\quad
R_{i}\triangleq\sup_{J\in\mathfrak{{J}}_{i}}\Pr_{\bm{{X}}\sim\mu_{J}}[\text{
$\bm{{X}}$ avoids $A_{\bar{\lambda}}$ }].$

Since $I\in\mathfrak{{J}}_{i}$ for all $i\geq 1$, it always holds that
$P\in[L_{i},R_{i}]$. In particular, $P=L_{i}=R_{i}$ when $L_{1}=R_{i}$. And by
Lemma 3.10, we have ${R_{i}}-{L_{i}}\leq 4\zeta_{0}^{i}$ for all $i\geq 1$.

Let $i_{\max}$ denote the smallest integer $i\geq 1$ with
$B_{\ell_{0}+\ell_{i}}(\Lambda)=V$. Let $j_{\max}$ denote the smallest integer
$i\geq 1$ with $L_{i}=R_{i}$. Observe that $j_{\max}\leq i_{\max}$. Then, the
while loop stops within at most $j_{\max}$ iterations. Moreover, for $1\leq
i\leq j_{\max}$, the values of $L_{i}$ and $R_{i}$ are computed in Algorithm 2
in the $i$-th iteration.

The probability of $\mathcal{F}_{1}$ is then calculated. By convention, assume
$L_{0}=0$ and $R_{0}=1$. It holds that

$\displaystyle\Pr[\mathcal{F}_{1}]$ $\displaystyle=\sum_{1\leq i\leq
i_{\max}}\Pr\left[\left(\rho<\max_{0\leq j\leq
i}L_{j}\right)\wedge\left(\max_{0\leq j<i}L_{j}\leq\rho<\min_{0\leq
j<i}R_{j}\right)\right]$ $\displaystyle=\sum_{1\leq i\leq
i_{\max}}\frac{\max_{0\leq j\leq i}L_{j}-\max_{0\leq j<i}L_{j}}{\min_{0\leq
j<i}R_{j}-\max_{0\leq j<i}L_{j}}\cdot\left(\min_{0\leq j<i}R_{j}-\max_{0\leq
j<i}L_{j}\right)$ $\displaystyle=\sum_{1\leq i\leq i_{\max}}\left(\max_{0\leq
j\leq i}L_{j}-\max_{0\leq j<i}L_{j}\right)=\max_{0\leq i\leq
i_{\max}}L_{i}=P.$

As for the probability of $\overline{\mathcal{F}_{1}}$, it holds that

$\displaystyle\Pr[\overline{\mathcal{F}_{1}}]$ $\displaystyle=\sum_{1\leq
i\leq i_{\max}}\Pr\left[\left(\rho\geq\min_{0\leq j\leq
i}R_{j}\right)\wedge\left(\max_{0\leq j<i}L_{j}\leq\rho<\min_{0\leq
j<i}R_{j}\right)\right]$ $\displaystyle=\sum_{1\leq i\leq
i_{\max}}\frac{\min_{0\leq j<i}R_{j}-\min_{0\leq j\leq i}R_{j}}{\min_{0\leq
j<i}R_{j}-\max_{0\leq j<i}L_{j}}\cdot\left(\min_{0\leq j<i}R_{j}-\max_{0\leq
j<i}L_{j}\right)$ $\displaystyle=\sum_{1\leq i\leq i_{\max}}\left(\min_{0\leq
j<i}R_{j}-\min_{0\leq j\leq i}R_{j}\right)=1-\min_{0\leq i\leq
i_{\max}}R_{i}=1-P.\qed$

The following claim guarantees the soundness of Algorithm 2 in Algorithm 2.

######  Claim 7.2.

With probability 1, $\max f>0$ and $\nu\left(\Omega_{\hat{I}}^{Y_{S}\wedge
Y_{T}}\right)>0$, where $f$ is defined in (9).

###### Proof.

Let $S=\mathsf{vbl}(\Lambda)$ and
$T=U\setminus\mathsf{vbl}(B_{\ell_{0}(\epsilon,\gamma,\delta)}(\Lambda))$. We
show that for any $\sigma_{1}\in\Sigma_{S}$ and $\tau_{1}\in\Sigma_{T}$ with
$\Pr[Y_{S}=\sigma_{1}\wedge Y_{T}=\tau_{1}]>0$, it always holds that
$\nu\left(\Omega_{\hat{I}}^{\sigma_{1}\wedge\sigma_{2}}\right)>0$, and
furthermore, it holds that $\max f>0$ conditioned on $Y_{S}=\sigma_{1}$, which
will prove the claim. Fix any $\sigma_{1}\in\Sigma_{S}$ and
$\tau_{1}\in\Sigma_{T}$ with $\Pr[Y_{S}=\sigma_{1}\wedge Y_{T}=\tau_{1}]>0$.
Since the input to _RecursiveSampling_ satisfies 3.9, it holds that
$(\bm{{Y}},\\{\Lambda\\})$ satisfies the clustered conditional Gibbs property
on instance $I$ with parameter $(\epsilon,\gamma,\delta)$, which means
$\mu^{\sigma_{1}}_{\hat{I},T}(\tau_{1})>0$, and hence
$\nu\left(\Omega_{\hat{I}}^{\sigma_{1}\wedge\tau_{1}}\right)>0$, for the LLL
instance $\hat{I}$ defined as in (8).

For $\nu\left(\Omega_{\hat{I}}\right)\geq\alpha-\delta>0$, there exist
$\sigma_{2}\in\Sigma_{S}$ and $\tau_{2}\in\Sigma_{T}$ such that
$\nu\left(\Omega^{\tau_{2}}_{\hat{I}}\right)>0$ and
$\nu\left(\Omega^{\sigma_{2}\wedge\tau_{2}}_{\hat{I}}\right)>0$. According to
Lemma 3.1, we have that $S$ and $T$ are $\epsilon$-correlated in instance
$\hat{I}$, i.e.:

$\nu\left(\Omega^{\sigma_{1}\wedge\tau_{1}}_{\hat{I}}\right)\cdot\nu\left(\Omega_{\hat{I}}^{\sigma_{2}\wedge\tau_{2}}\right)\leq(1+\epsilon)\cdot\nu\left(\Omega^{\sigma_{1}\wedge\tau_{2}}_{\hat{I}}\right)\cdot\nu\left(\Omega_{\hat{I}}^{\sigma_{2}\wedge\tau_{1}}\right).$

Thus, it holds that
$\nu\left(\Omega^{\sigma_{1}\wedge\tau_{2}}_{\hat{I}}\right)>0$ and $\max
f\geq
f(\tau_{2})=\nu\left(\Omega^{\tau_{2}}_{\hat{I}}\right)/{\nu\left(\Omega^{\sigma\wedge\tau_{2}}_{\hat{I}}\right)}>0$.
∎

######  Claim 7.3.

Conditioned on $\mathcal{F}_{1}$, when _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ returns, $\bm{{Y}}$
follows $\mu_{\hat{I}}$.

###### Proof.

By 7.2, the Bayes filter constructed in Algorithm 2 is well-defined. Let
$\mathcal{F}_{2}$ denote the event that the Bayes filter defined in Algorithm
2 succeeds. Depending on whether $\mathcal{F}_{2}$ happens, we proceed in two
cases.

First, assume that $\mathcal{F}_{2}$ does not happen. In this case, we only
need to verify that the input of the recursive call _RecursiveSampling_
$\left(\bm{{Y}};\hat{I},B_{r}(\Lambda)\cup\\{\lambda\\},\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2},\frac{\alpha}{2}\right)$
in Algorithm 2 satisfies 3.9. For any fixed $x\in\mathbb{N}^{+}$ with
$\Pr[\mathcal{F}_{1}\wedge\neg\mathcal{F}_{2}\wedge r=x]>0$, conditioned on
$\mathcal{F}_{1}\wedge\neg\mathcal{F}_{2}\wedge r=x$, the properties asserted
in 3.9 are verified one by one on the input to this recursive call as follow.

  1. 1.

By our assumption, the original input
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ satisfies 3.9, which
means $0<\epsilon\leq\frac{1}{2}$, $0<\alpha\leq\gamma<1$ and
$0<\delta<\zeta_{0}\cdot\alpha$. The same can be easily verified for
$\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2},\frac{\alpha}{2}\right)$.

  2. 2.

Since $(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ satisfies 3.9, the
LLL instance $I(V\setminus\Lambda)$ is $\gamma$-satisfiable. For
$x>\ell_{0}(\epsilon,\gamma,\delta)$, we have
$\hat{I}((V\cup\\{\lambda\\})\setminus(B_{x}(\Lambda)\cup\\{\lambda\\}))=I(V\setminus
B_{x}(\Lambda))$, which must also be $\gamma$-satisfiable since $V\setminus
B_{x}(\Lambda)\subseteq V\setminus\Lambda$. Furthermore, it holds that
$\nu(\Omega_{\hat{I}})\geq\alpha-\delta\geq(1-\zeta_{0})\alpha$. By choosing
$\zeta_{0}>0$ to be a sufficient small constant, the LLL instance $\hat{I}$ is
at least $\frac{\alpha}{2}$-satisfiable.

  3. 3.

Let $\hat{S}=\mathsf{vbl}(B_{x}(\Lambda))$ and
$\hat{T}=U\setminus\mathsf{vbl}(B_{x+\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}\right)}(\Lambda))$.
Let $A_{\kappa}$ and $\hat{I}_{\kappa}$, where $\kappa\not\in V$, respectively
denote the bad event and the augmented LLL instance constructed in Lemma 3.1,
where

$A_{\kappa}\triangleq
A^{{\hat{I}}}_{\bm{\lambda}({B_{x}(\Lambda)},{\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}})},\quad\text{
and }\quad\hat{I}_{\kappa}\triangleq(\\{X_{i}\\}_{i\in U},\\{A_{v}\\}_{v\in
V}\cup\\{A_{\lambda}\\}\cup\\{A_{\kappa}\\}).$

Let $\mathcal{A}$ denote the event that $\bm{{Y}}$ avoids the bad event
$A_{\kappa}$. For any $\sigma\in\Sigma_{\hat{S}}$ with
$\Pr[\mathcal{F}_{1}\wedge\neg\mathcal{F}_{2}\wedge r=x\wedge
Y_{\hat{S}}=\sigma]>0$, since $Y_{\hat{S}}=\sigma$ already ensures $r_{1}\geq
x$, we have

$\mathcal{F}_{1}\wedge\neg\mathcal{F}_{2}\wedge r=x\wedge
Y_{\hat{S}}=\sigma\iff\mathcal{F}_{1}\wedge\neg\mathcal{F}_{2}\wedge\mathcal{A}\wedge
Y_{\hat{S}}=\sigma.$

Moreover, given $\mathcal{A}$ and $Y_{\hat{S}}=\sigma$, the event
$\neg\mathcal{F}_{2}$ is conditionally independent of $Y_{\hat{T}}$. Recall
that $(\bm{{Y}},\\{\Lambda\\})$ satisfies the clustered conditional Gibbs
property on instance $I$ with parameter $(\epsilon,\gamma,\delta)$. Thus,
conditioned on $\mathcal{F}_{1}\wedge\neg\mathcal{F}_{2}\wedge r=x\wedge
Y_{\hat{S}}=\sigma$, it holds that $Y_{\hat{T}}$ follows the distribution
$\mu^{\sigma}_{\hat{I}_{1},\hat{T}}$. Thus,
$(\bm{{Y}},\\{B_{x}(\Lambda)\cup\\{\lambda\\}\\})$ is clustered conditional
Gibbs on instance $\hat{I}$ with parameter
$\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}\right)$.

Altogether, conditioned on $\mathcal{F}_{1}\land\neg\mathcal{F}_{2}\land r=x$,
the input to the recursive call in Algorithm 2 satisfies 3.9. By the induction
hypothesis, right after the recursive call in Algorithm 2 returns, $\bm{{Y}}$
follows the distribution $\mu_{\hat{I}}$. Since this holds for all possible
$x\in\mathbb{N}^{+}$, we have that the output $\bm{{Y}}\sim\mu_{\hat{I}}$
conditioned on $\mathcal{F}_{1}$ and $\neg\mathcal{F}_{2}$.

The remaining case is that $\mathcal{F}_{2}$ happens. Let
$S=\mathsf{vbl}(\Lambda)$ and
$T=U\setminus\mathsf{vbl}(B_{\ell_{0}(\epsilon,\gamma,\delta)}(\Lambda))$. Fix
any $\sigma\in\Sigma_{S}$ with $\Pr[\mathcal{F}_{1}\wedge\mathcal{F}_{2}\wedge
Y_{S}=\sigma]>0$. We prove that, conditioned on
$\mathcal{F}_{1}\land\mathcal{F}_{2}\land Y_{S}=\sigma$, the $\bm{{Y}}$
follows the distribution $\mu_{\hat{I}}$ after Algorithm 2 being executed. In
the following analysis, let $\bm{{Y}}=(Y_{i})_{i\in U}$ denote the original
input random assignment and let $\bm{{Y}}^{\prime}=(Y^{\prime}_{i})_{i\in U}$
denote the $\bm{{Y}}$ after Algorithm 2 being executed.

Recall that $S$ and $T$ are $\epsilon$-correlated in instance $\hat{I}$. For
any $\pi\in\Sigma$ with $\nu(\Omega_{\hat{I}}^{\pi_{T}\wedge\sigma})=0$, it
holds that $\mu_{\hat{I},T}(\pi_{T})=0$. Thus, for any $\pi\in\Sigma$ with
$\mu_{\hat{I},T}(\pi_{T})>0$, it holds that
$\nu(\Omega_{\hat{I}}^{\pi_{T}\wedge\sigma})>0$. For any $\pi\in\Sigma$ with
$\mu_{\hat{I}}(\pi)>0$, conditioned on $\mathcal{F}_{1}$ and $Y_{S}=\sigma$,
it holds that

$\displaystyle\Pr[\bm{{Y}}^{\prime}=\pi\wedge\mathcal{F}_{2}]$
$\displaystyle=\Pr[Y^{\prime}_{T}=\pi_{T}]\cdot\Pr[Y^{\prime}_{U\setminus
T}=\pi_{U\setminus T}\mid
Y^{\prime}_{T}=\pi_{T}]\cdot\Pr[\mathcal{F}_{2}\mid\bm{{Y}}^{\prime}=\pi]$
$\displaystyle=\mu^{\sigma}_{\hat{I},T}(\pi_{T})\cdot\mu^{\pi_{T}}_{\hat{I},U\setminus
T}(\pi_{U\setminus
T})\cdot\frac{\nu\left(\Omega_{\hat{I}}^{\pi_{T}}\right)}{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\pi_{T}}\right)}\cdot\frac{1}{\max
f}=\mu_{\hat{I}}(\pi)\cdot\frac{\nu\left(\Omega_{\hat{I}}\right)}{\nu\left(\Omega_{\hat{I}}^{\sigma}\right)}\cdot\frac{1}{\max
f}.$

Then, conditioned on $\mathcal{F}_{1}$ and $Y_{S}=\sigma$, it holds that

$\Pr[\mathcal{F}_{2}]=\sum_{\pi\in\Sigma}\Pr[\bm{{Y}}^{\prime}=\pi\wedge\mathcal{F}_{2}]=\sum_{\pi\in\Sigma}\mu_{\hat{I}}(\pi)\cdot\frac{\nu\left(\Omega_{\hat{I}}\right)}{\nu\left(\Omega_{\hat{I}}^{\sigma}\right)}\cdot\frac{1}{\max
f}=\frac{\nu\left(\Omega_{\hat{I}}\right)}{\nu\left(\Omega_{\hat{I}}^{\sigma}\right)}\cdot\frac{1}{\max
f}.$

Thus, conditioned on $\mathcal{F}_{1}\land\mathcal{F}_{2}\land Y_{S}=\sigma$,
the output $\bm{{Y}}^{\prime}$ follows $\mu_{\hat{I}}$. By the law of total
probability, conditioned on $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, after
_RecursiveSampling_ $(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$
returns, $\bm{{Y}}$ follows $\mu_{\hat{I}}$. ∎

######  Claim 7.4.

Conditioned on $\overline{\mathcal{F}_{1}}$, when _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ returns, $\bm{{Y}}$
follows $\mu_{\hat{I}^{\prime}}$.

###### Proof.

In this case, we only need verify that the input
$\left(\bm{{Y}};\hat{I}^{\prime},B_{s}(\Lambda)\cup\left\\{\overline{\lambda}\right\\},\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-\hat{R})}{2},\alpha(1-R)\right)$
of the recursive call to _RecursiveSampling_ in Algorithm 2 satisfies 3.9. For
any fixed $x\in\mathbb{N}^{+}$ with $\Pr(\overline{\mathcal{F}_{1}}\wedge
s=x)>0$, conditioned on $\overline{\mathcal{F}_{1}}$ and $s=x$, the properties
asserted in 3.9 are verified one by one on the input to this recursive call as
follow.

  1. 1.

By our assumption, the original input
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ satisfies 3.9, which
means $0<\epsilon\leq\frac{1}{2}$, $0<\alpha\leq\gamma<1$ and
$0<\delta<\zeta_{0}\cdot\alpha$. The same can be verified on
$\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-\hat{R})}{2},\alpha(1-R)\right)$.

  2. 2.

Since $(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ satisfies 3.9, the
LLL instance $I(V\setminus\Lambda)$ is $\gamma$-satisfiable. For
$x>\ell_{0}(\epsilon,\gamma,\delta)$, we have
$\hat{I}^{\prime}((V\cup\\{\bar{\lambda}\\})\setminus(B_{x}(\Lambda)\cup\\{\bar{\lambda}\\}))=I(V\setminus
B_{x}(\Lambda))$, which must also be $\gamma$-satisfiable since $V\setminus
B_{x}(\Lambda)\subseteq V\setminus\Lambda$. Furthermore, it holds that
$\nu(\Omega_{\hat{I}^{\prime}})\geq\nu(\Omega_{I})\cdot(1-P)\geq\alpha\cdot(1-R)$.

  3. 3.

Let $\hat{S}=\mathsf{vbl}(B_{x}(\Lambda))$ and
$\hat{T}=U\setminus\mathsf{vbl}(B_{x+\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}\right)}(\Lambda))$.
Let $A_{\kappa}$ and $\hat{I}_{\kappa}$, where $\kappa\not\in V$, respectively
denote the bad event and the augmented LLL instance constructed in Lemma 3.1,
where

$A_{\kappa}\triangleq
A^{{\hat{I}^{\prime}}}_{\bm{\lambda}({B_{x}(\Lambda)},{\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}})},\quad\text{
and }\quad\hat{I}_{1}^{\prime}\triangleq(\\{X_{i}\\}_{i\in
U},\\{A_{v}\\}_{v\in V}\cup\\{A_{\bar{\lambda}}\\}\cup\\{A_{\kappa}\\}\\}.$

Let $\mathcal{A}$ denote the event that $\bm{{Y}}$ avoids the bad event
$A_{\kappa}$. For any $\sigma\in\Sigma_{\hat{S}}$ with
$\Pr[\overline{\mathcal{F}_{1}}\wedge s=x\wedge Y_{\hat{S}}=\sigma]>0$, since
$Y_{\hat{S}}=\sigma$ already ensures $s\geq x$, we have

$\overline{\mathcal{F}_{1}}\wedge s=x\wedge
Y_{\hat{S}}=\sigma\iff\neg\overline{\mathcal{F}_{1}}\wedge\mathcal{A}\wedge
Y_{\hat{S}}=\sigma.$

Recall that by our assumption, $(\bm{{Y}},\\{\Lambda\\})$ satisfies the
clustered conditional Gibbs property on instance $I$ with parameter
$(\epsilon,\gamma,\delta)$. Thus, conditioned on
$\overline{\mathcal{F}_{1}}\wedge s=x\wedge Y_{\hat{S}}=\sigma$, it holds that
$Y_{\hat{T}}$ follows the distribution
$\mu^{\sigma}_{\hat{I}_{1}^{\prime},\hat{T}}$, i.e.
$(\bm{{Y}},\\{B_{x}(\Lambda)\cup\\{\overline{\lambda}\\}\\})$ satisfies the
clustered conditional Gibbs property on instance $\hat{I}^{\prime}$ with
parameter $\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}\right)$.

Altogether, conditioned on $\overline{\mathcal{F}_{1}}$ and $r=x$, the input
to the recursive call in Algorithm 2 satisfies 3.9. By the induction
hypothesis, right after the recursive call in Algorithm 2 returns, $\bm{{Y}}$
follows the distribution $\mu_{\hat{I}}$. Since this holds for all possible
$x\in\mathbb{N}^{+}$, by the law of total probability, we have that the output
$\bm{{Y}}\sim\mu_{\hat{I}^{\prime}}$ conditioned on
$\overline{\mathcal{F}_{1}}$. ∎

Now we are ready to finalize the proof of the correctness of
_RecursiveSampling_. Denote by $\bm{{Y}}^{*}$ the random assignment $\bm{{Y}}$
when _RecursiveSampling_ $(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$
returns. By 7.1 and 7.3, for any $\pi\in\Sigma_{V}$ avoiding $A_{\lambda}$, it
holds that

$\displaystyle\Pr[\bm{{Y}}^{*}=\pi]$
$\displaystyle=\Pr[\bm{{Y}}^{*}=\pi\mid\mathcal{F}_{1}]\cdot\Pr[\mathcal{F}_{1}]+\Pr[\bm{{Y}}^{*}=\pi\mid\overline{\mathcal{F}_{1}}]\cdot\Pr[\overline{\mathcal{F}_{1}}]$
$\displaystyle=\mu_{\hat{I}}(\pi)\cdot P=\mu_{I}(\pi).$

On the other hand, by 7.1 and 7.4, for any $\pi\in\Sigma_{V}$ not avoiding
$A_{\lambda}$, it holds that

$\displaystyle\Pr[\bm{{Y}}^{*}=\pi]$
$\displaystyle=\Pr[\bm{{Y}}^{*}=\pi\mid\mathcal{F}_{1}]\cdot\Pr[\mathcal{F}_{1}]+\Pr[\bm{{Y}}^{*}=\pi\mid\overline{\mathcal{F}_{1}}]\cdot\Pr[\overline{\mathcal{F}_{1}}]$
$\displaystyle=\mu_{\hat{I}^{\prime}}(\pi)\cdot(1-P)=\mu_{I}(\pi).$

This proves that $\bm{{Y}}\sim\mu_{I}$ when _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ returns, assuming 3.9
satisfied initially by the input, which finishes the inductive proof of the
correctness of _RecursiveSampling_.

###  7.2 Efficiency of _RecursiveSampling_ (Proof of Item 2 in Lemma 3.11)

We now prove Item 2 of Lemma 3.11, which bounds the efficiency of Algorithm 2.

Assume that 3.9 is satisfied by the input of _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$. To upper bound the
complexity of the recursive algorithm, we construct a potential
$\mathcal{P}\geq 0$, which is computed during the execution of
_RecursiveSampling_ according to the following rules which are added into
Algorithm 2:

  * •

$\mathcal{P}$ is initialized to $0$, and the current value of $\mathcal{P}$ is
returned whenever the algorithm returns;

  * •

when the recursive call in Algorithm 2 returns with some value
$\mathcal{P}_{1}$, the value of $\mathcal{P}$ is increased by
$\mathcal{P}_{1}$;

  * •

when the recursive call in Algorithm 2 returns with some value
$\mathcal{P}_{2}$, the current value of $\mathcal{P}$ is increased by
$\mathcal{P}_{2}+\lceil\log\frac{1}{1-R}\rceil+1$, where $R$ is the current
estimation upper bound calculated in Algorithm 2;

  * •

whenever Algorithm 2 is executed, the value of $\mathcal{P}$ is increased by
1.

This procedure for computing the potential $\mathcal{P}$ is explicitly
described in Algorithm 5. Note that other than the part for computing the
value of $\mathcal{P}$, Algorithm 5 is exactly the same as Algorithm 2.
Therefore, we refer to them both by the same name _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$.

1

Input : LLL instance $I=\left(\\{X_{i}\\}_{i\in U},\\{A_{v}\\}_{v\in
V}\right)$, subset $\Lambda\subseteq V$, parameter
$(\epsilon,\gamma,\delta,\alpha)$;

Data : assignment $\bm{{Y}}=(Y_{i})_{i\in U}$ stored globally that can be
updated by the algorithm;

Output : integer $\mathcal{P}\geq 0$;

2

// An integer $\mathcal{P}\geq 0$ is computed and returned (which are
highlighted); otherwise, the algorithm is the same as Algorithm 2.

3

4

5initialize $\mathcal{P}\leftarrow 0$, $i\leftarrow 1$, and define
$\ell_{0}\triangleq\ell_{0}(\epsilon,\gamma,\delta)$;

6

// The value of $\mathcal{P}$ is initialized to 0.

7

8draw $\rho\in[0,1)$ uniformly at random;

9

10while  _true_ do

11

12
${\ell}_{i}\leftarrow\ell_{0}\left(\zeta_{0}^{i},\gamma,\alpha\cdot\zeta_{0}^{i}\right)$;

13

14 compute the smallest interval $[{L},{R}]$ containing
$P\triangleq\Pr_{\bm{{X}}\sim\mu_{I}}[\,\bm{{X}}\text{ avoids }A_{\lambda}\,]$
based on $\Lambda$, $A_{\lambda}$,
$I\left(B_{\ell_{0}+{\ell}_{i}+1}(\Lambda)\right)$, assuming that $I$ is
$\alpha$-satisfiable and $I\left(V\setminus
B_{\ell_{0}+{\ell}_{i}+1}(\Lambda)\right)$ is $\gamma$-satisfiable;

15

16 if  _$\rho <{L}$ _ then

17

18 define $T\triangleq U\setminus\mathsf{vbl}(B_{\ell_{0}}(\Lambda))$;

19

20 with probability  _$\frac{f\left(Y_{T}\right)}{\max f}$ , where $f$ is
defined as in (9), _ do

21 update $\bm{{Y}}$ by redrawing $Y_{U\setminus T}\sim\mu_{\hat{I},U\setminus
T}^{Y_{T}}$;

22

23 else

24 initialize $r\leftarrow\ell_{0}+1$;

25

26 while  _$\bm{{Y}}$ does not avoid the bad event
$A^{{\hat{I}}}_{\bm{\lambda}({B_{r}(\Lambda)},{{1}/{2},\,\gamma,\,{\zeta_{0}\alpha}/{2}})}$_
do

27 grow the ball: $r\leftarrow
r+\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}\right)$ and
$\mathcal{P}\leftarrow\mathcal{P}+1$;

28

// The value of $\mathcal{P}$ is increased by 1.

29

30

31 $\mathcal{P}\leftarrow\mathcal{P}\,+\,$_RecursiveSampling_
$\left(\bm{{Y}};\hat{I},B_{r}(\Lambda)\cup\\{\lambda\\},\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2},\frac{\alpha}{2}\right)$;

32

// The value of $\mathcal{P}$ is increased by the amount returned by the
recursive call.

33

34

35 return _$\mathcal{P}$_ ;

36

37 else if  _$\rho\geq{R}$ _ then

38

39 initialize $s\leftarrow\ell_{0}+1$;

40

41 while  _$\bm{{Y}}$ does not avoid the bad event
$A^{{\hat{I}^{\prime}}}_{\bm{\lambda}({B_{s}(\Lambda)},{1/2,\,\gamma,\,{\zeta_{0}\alpha(1-R)}/{2}})}$
_ do

42 grow the ball: $s\leftarrow
s+\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}\right)$ and
$\mathcal{P}\leftarrow\mathcal{P}+1$;

43

// The value of $\mathcal{P}$ is increased by 1.

44

45
$\mathcal{P}\leftarrow\mathcal{P}+\lceil\log\frac{1}{1-R}\rceil+$_RecursiveSampling_
$\left(\bm{{Y}};\hat{I}^{\prime},B_{s}(\Lambda)\cup\left\\{\overline{\lambda}\right\\},\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2},\alpha(1-R)\right)$;

46

// The value of $\mathcal{P}$ is increased by the amount returned by the
recursive call.

47

48 return _$\mathcal{P}$_ ;

49

50 else

51

52 enter the next iteration (and refine the estimation of $P$): $i\leftarrow
i+1$ and $\mathcal{P}\leftarrow\mathcal{P}+1$;

53

// The value of $\mathcal{P}$ is increased by 1.

54

55

Algorithm 5 _RecursiveSampling_($\bm{{Y}}$;
$I,\Lambda,\epsilon,\gamma,\delta,\alpha$) that computes $\mathcal{P}$ during
execution

Next, we prove 7.5 and 7.6, where 7.5 says that the potential $\mathcal{P}$
computed as above can be used to bound the radius $r$ of _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ stated in Item 2 of Lemma
3.11, and 7.6 gives an upper bound on the potential $\mathcal{P}$.

######  Claim 7.5.

Suppose that 3.9 is satisfied by the input of _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$, who accesses
$I(B_{r}(\Lambda))$, updates $Y_{\mathsf{vbl}(B_{r}(\Lambda))}$, and returns a
$\mathcal{P}\geq 0$. It holds that

$r\leq\ell_{0}(\epsilon,\gamma,\delta)+O\left(\mathcal{P}\cdot\left(\mathcal{P}+\log\frac{1}{\alpha}\right)\cdot\log\frac{1}{\gamma}\cdot\log\left(\mathcal{P}\log\frac{1}{\gamma}\log\frac{1}{\alpha}\right)\right).$

###### Proof.

Let $c>1$ be a sufficient large constant. For $\mathcal{P}\in\mathbb{N}$,
$\gamma\in(0,1)$, $\alpha\in(0,1)$, define

$g(\mathcal{P},\gamma,\alpha)=c\cdot\mathcal{P}\cdot\left(\mathcal{P}+\log\frac{1}{\alpha}\right)\cdot\log\frac{1}{\gamma}\cdot\log\left(\mathcal{P}\log\frac{1}{\gamma}\log\frac{1}{\alpha}\right).$

7.5 is proved by showing that
$r\leq\ell_{0}(\epsilon,\gamma,\delta)+g(\mathcal{P},\gamma,\alpha)$. This is
proved by a structural induction. Suppose that the input is the LLL instance
$I=\left(\\{X_{i}\\}_{i\in U},\\{A_{v}\\}_{v\in V}\right)$, the random
assignment $\bm{{Y}}=(Y_{i})_{i\in U}$, and the subset $\Lambda\subseteq V$ of
bad events, along with the parameter $(\epsilon,\gamma,\delta,\alpha)$
satisfying 3.9.

First, for the induction basis, when $\Lambda=V$, the induction hypothesis
holds as $r=0$ and $\mathcal{P}=0$.

Now, consider the general case. Define

$\displaystyle\ell$
$\displaystyle\triangleq\ell_{0}(\epsilon,\gamma,\delta)=O\left(\log\frac{1}{\epsilon}\log\frac{1}{\gamma}\log\frac{1}{\delta}\log\left(\log\frac{1}{\epsilon}\log\frac{1}{\gamma}\log\frac{1}{\alpha}\right)\right),$
$\displaystyle\ell_{1}$
$\displaystyle\triangleq\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}\right)=O\left(\log\frac{1}{\gamma}\log\frac{1}{\alpha}\log\left(\log\frac{1}{\gamma}\log\frac{1}{\alpha}\right)\right),$
$\displaystyle\ell_{2}$
$\displaystyle\triangleq\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}\right)=O\left(\log\frac{1}{\gamma}\log\frac{1}{\alpha(1-R)}\log\left(\log\frac{1}{\gamma}\log\frac{1}{\alpha(1-R)}\right)\right),$
$\displaystyle\ell_{3}$
$\displaystyle\triangleq\ell_{0}\left(\zeta_{0}^{K},\gamma,\alpha\cdot\zeta_{0}^{K}\right)=O\left(K\log\frac{1}{\gamma}\left(\log\frac{1}{\alpha}+K\right)\log\left(K\log\frac{1}{\gamma}\left(\log\frac{1}{\alpha}+K\right)\right)\right),$
where $K$ stands for the number of times that Algorithm 5 is executed.

The induction then proceeds in the following three cases:

  * •

Case 1: Algorithm 5 is executed. Let $K_{1}$ denote the number of times that
Algorithm 5 is executed. Let $\mathcal{P}_{1}$ denote the value returned by
the recursive call in Algorithm 5. In this case, we have
$\mathcal{P}=K+\mathcal{P}_{1}+K_{1}$. By the induction hypothesis, it holds
that

$r\leq\ell+(K_{1}+1)\cdot\ell_{1}+g\left(\mathcal{P}_{1},\gamma,\frac{\zeta_{0}\alpha}{2}\right)+\ell_{3}.$

  * •

Case 2: Algorithm 2 is executed.  Let $K_{2}$ denote the number of times that
Algorithm 5 is executed. Let $\mathcal{P}_{2}$ denote the value returned by
the recursive call in Algorithm 5. In this case we have
$\mathcal{P}=K+\mathcal{P}_{2}+K_{2}+\lceil\log\frac{1}{1-R}\rceil$. By the
induction hypothesis, it holds that

$r\leq\ell+(K_{2}+1)\cdot\ell_{2}+g\left(\mathcal{P}_{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}\right)+\ell_{3}.$

  * •

Case 3: otherwise.  In this case, we have $\mathcal{P}=K$. It holds that

$r\leq\ell+\ell_{3}+1.$

By choosing $c$ to be a large enough constant, one can verify that
$r\leq\ell_{0}+g(\mathcal{P},\gamma,\alpha)$ in all cases. ∎

######  Claim 7.6.

Suppose that 3.9 is satisfied by the input of _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$, who returns a
$\mathcal{P}\geq 0$. For any $\eta\in(0,1)$, with probability at least
$1-\eta$, it holds that $\mathcal{P}=O\left(\log^{2}\frac{1}{\eta}\right)$.

###### Proof.

We prove that, for some constant $d_{1}$, it holds that
$\Pr[\mathcal{P}>d_{1}\cdot\log^{2}\frac{1}{\eta}]<\eta$ for any
$\eta\in(0,1)$.

This is proved by induction. Suppose that the input is the LLL instance
$I=\left(\\{X_{i}\\}_{i\in U},\\{A_{v}\\}_{v\in V}\right)$, the random
assignment $\bm{{Y}}=(Y_{i})_{i\in U}$, and the subset $\Lambda\subseteq V$ of
bad events, along with the parameter $(\epsilon,\gamma,\delta,\alpha)$
satisfying 3.9.

For the induction basis, when $\Lambda=V$, the induction hypothesis holds
trivially since $\mathcal{P}=0$.

For the general case. by induction hypothesis, all recursive calls return the
correctly bounded values of $\mathcal{P}$’s as long as 3.9 is satisfied by the
input. We prove that _RecursiveSampling_
$(\bm{{Y}};I,\Lambda,\epsilon,\gamma,\delta,\alpha)$ returns a correctly
bounded $\mathcal{P}$.

Let $K$ denote the number of times that Algorithm 5 is executed. Let $K_{1}$
denote the number of times that Algorithm 5 is executed. Let $K_{2}$ denote
the number of times that Algorithm 5 is executed. If Algorithm 5 is executed,
let $\mathcal{P}_{1}$ denote the value returned by the recursive call in
Algorithm 5. If Algorithm 5 is executed, let $\mathcal{P}_{2}$ denote the
value returned by the recursive call in Algorithm 5.

For $\eta\in(0,1)$, let $k\triangleq 10\log\frac{1}{\eta}+d_{2}$ for
sufficient large constant $d_{2}$. One can verify that if
$\mathcal{P}>d_{1}\cdot\log^{2}\frac{1}{\eta}$, then necessarily at least one
of the following events must have happened.

  * •

Event $\mathcal{E}_{1}$: $K>k$. The probability that Algorithm 5 is executed
more that $k$ times is $R-L$, where $R$ and $L$ respectively take values of
these variables in the $k$-th iteration of the while loop. By Lemma 3.10, we
have $R-L\leq 4\zeta_{0}^{k}$. By choosing $\zeta_{0}$ to be a small enough
constant, we have

$\Pr(\mathcal{E}_{1})=\Pr(K>k)\leq 4\zeta_{0}^{k}\leq 0.01\eta.$

  * •

Event $\mathcal{E}_{2}$: Algorithm 5 is executed and $K_{1}\geq k$. We have
$\Pr(\mathcal{E}_{2})\leq\Pr\left(\forall A\in\Phi:\text{$A$ occurs on
$\bm{{Y}}$}\right)$, where

$\Phi\triangleq\left\\{A^{{\hat{I}}}_{\bm{\lambda}({B_{r}(\Lambda)},{\frac{1}{2},\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}})}~{}\middle|~{}r=\ell_{0}(\epsilon,\gamma,\delta)+1+i\cdot\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha}{2}\right)\text{,
for }0\leq i<k\right\\}.$

Let $X_{\beta}$ and $A_{\kappa}$ denote the respective random variable and bad
event constructed in Lemma 3.12 under parameter $\Lambda$,
$Y_{\mathsf{vbl}(\Lambda)}$, $(\epsilon,\gamma,\delta)$,
$I(B_{\ell(\epsilon,\gamma,\delta)+1}(\Lambda))$. Define

$\displaystyle U^{\prime}\triangleq
U\setminus\mathsf{vbl}(B_{\ell_{0}(\epsilon,\gamma,\delta)}(\Lambda)),$ (13)
$\displaystyle V^{\prime}\triangleq V\setminus
B_{\ell_{0}(\epsilon,\gamma,\delta)+1}(\Lambda),$ $\displaystyle
I^{\prime}\triangleq\left(\\{X_{i}\\}_{i\in
U^{\prime}}\cup\\{X_{\beta}\\},\\{A_{v}\\}_{v\in
V^{\prime}}\cup\\{A_{\kappa}\\}\right).$

Let $Y_{\beta}$ be drawn independent according to the marginal distribution
$\mu^{Y_{\mathsf{vbl}(\kappa)\setminus\\{\beta\\}}}_{I^{\prime},\beta}$. This
is well-defined because $Y_{\mathsf{vbl}(\kappa)\setminus\\{\beta\\}}\subseteq
U^{\prime}$. Then, define assignment $\bm{{Y}}^{\prime}$ as

$\displaystyle\bm{{Y}}^{\prime}\triangleq Y_{U^{\prime}}\land Y_{\beta}.$ (14)

Since $(\bm{{Y}},{\Lambda})$ satisfies the clustered conditional Gibbs
property on $I$ with parameter $(\epsilon,\gamma,\delta)$, we have
$Y_{U^{\prime}}\sim\mu^{Y_{\mathsf{vbl}(\Lambda)}}_{\hat{I},U^{\prime}}$,
where $\hat{I}$ is defined as in (8). By Lemma 3.12, we have
$Y_{U^{\prime}}\sim\mu_{I^{\prime},U^{\prime}}$, which means
$\bm{{Y}}^{\prime}\sim\mu_{I^{\prime}}$, i.e. for any $A\in\Phi$, we have that
$A$ occurs on $\bm{{Y}}$ if and only if $A$ occurs on $\bm{{Y}}^{\prime}$.
Thus,

$\displaystyle\Pr(\mathcal{E}_{2})$ $\displaystyle\leq\Pr\left(\forall
A\in\Phi:\text{$A$ occurs on $\bm{{Y}}$}\right)=\Pr\left(\forall
A\in\Phi:A\text{ occurs on }\bm{{Y}}^{\prime}\right)$
$\displaystyle\leq\frac{(\zeta_{0}\alpha)^{k}}{(1-\epsilon)(\alpha-\delta)}\leq
4\zeta_{0}^{k}\leq 0.01\eta,$

by choosing $\zeta_{0}$ to be sufficiently small constant.

  * •

Event $\mathcal{E}_{3}$: Algorithm 5 is executed and $\mathcal{P}_{1}\geq
d_{1}\log^{2}\frac{1}{1.1\eta}$. We first bound the probability that Algorithm
5 is executed. Recall that $S$ and $T$ are $\epsilon$-correlated in instance
$\hat{I}$, where $\hat{I}$ is defined as in (8). According to Definition 3.1,
it holds with probability $1$ that

$\frac{f(Y_{T})}{f_{\max}}\geq\frac{1}{1+\epsilon}\geq\frac{1}{2}.$

Thus, the probability that Algorithm 5 is executed is at most $\frac{1}{2}$.
By the induction hypothesis, we have
$\Pr(\mathcal{P}_{1}>d_{1}\cdot\log^{2}\frac{1}{1.1\eta}\mid\text{\lx@cref{creftypecap~refnum}{line:compute-
p-p1} is executed})<1.1\eta$. Overall, we have

$\Pr(\mathcal{E}_{3})\leq\frac{1}{2}\cdot 1.1\eta\leq 0.55\eta.$

  * •

Event $\mathcal{E}_{4}$: Algorithm 5 is executed and $K_{2}\geq k$. The
probability of $\mathcal{E}_{4}$ can be bounded similarly as
$\mathcal{E}_{2}$. Let $I^{\prime}$, $Y^{\prime}$ be defined as in (13) and
(14) respectively. Let $\hat{I}^{\prime}$ defined as in (8). Define

$\Phi^{\prime}\triangleq\left\\{A^{{\hat{I}^{\prime}}}_{\bm{\lambda}({B_{r}(\Lambda)},{\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}})}~{}\middle|~{}r=\ell_{0}(\epsilon,\gamma,\delta)+1+i\cdot\ell_{0}\left(\frac{1}{2},\gamma,\frac{\zeta_{0}\alpha(1-R)}{2}\right)\text{,
for }0\leq i<k\right\\}$

For any $A\in\Phi^{\prime}$, we have that $A$ occurs on $\bm{{Y}}$ if and only
if $A$ occurs on $\bm{{Y}}^{\prime}$, and

$\displaystyle\Pr(\mathcal{E}_{4})$ $\displaystyle\leq\Pr\left(\forall
A\in\Phi^{\prime}:\text{$A$ occurs on $\bm{{Y}}$}\right)=\Pr\left(\forall
A\in\Phi^{\prime}:\text{$A$ occurs on $\bm{{Y}}^{\prime}$}\right)$
$\displaystyle\leq\frac{(\zeta_{0}\alpha)^{k}}{(1-\epsilon)(\alpha-\delta)}\leq
4\zeta_{0}^{k}\leq 0.01\eta.$

  * •

Event $\mathcal{E}_{5}$: Algorithm 5 is executed and $\log\frac{1}{1-R}\geq
k$.  The probability that Algorithm 5 is executed given $R$, is precisely
$1-R$. Thus, we have

$\Pr(\mathcal{E}_{5})=\Pr\left(\text{
\lx@cref{creftypecap~refnum}{line:compute-p-p2} is executed
}~{}\middle|~{}\log\frac{1}{1-R}\geq
k\right)\cdot\Pr\left(\log\frac{1}{1-R}\geq k\right)\leq 2^{-k}\leq
0.01\epsilon.$

  * •

Event $\mathcal{E}_{6}$: Algorithm 5 is executed and
$\mathcal{P}_{2}>d_{1}\log^{2}\frac{1}{1.1\eta}$. The probability that
Algorithm 5 is executed is bounded by $1-R$. Recall that $1-R$ is the lower
bound of $P\triangleq\Pr_{\bm{{X}}\sim\mu_{I}}(\text{ $\bm{{X}}$ does not
avoids $A_{\lambda}$})$. Assuming 3.9, this probability $P$ is at most
$\frac{\delta}{\alpha}\leq\zeta_{0}$. By the induction hypothesis, we have
$\Pr(\mathcal{P}_{2}>d_{1}\cdot\log^{2}\frac{1}{1.1\eta})<1.1\eta$. And by
choosing $\zeta_{0}$ to be sufficiently small constant, we have

$\Pr(\mathcal{E}_{6})\leq\zeta_{0}\cdot 1.1\eta\leq 0.01\eta.$

By the union bound applied on all above cases, we have

$\Pr\left(\mathcal{P}>d_{1}\cdot\log^{2}\frac{1}{\eta}\right)<\eta,$

for any $\eta\in(0,1)$. This proves 7.6. ∎

Combine 7.5 and 7.6. For any $0<\eta<1$, with probability at least $1-\eta$,
the following upper bound holds for the radius $r$ of Algorithm 2, assuming
that its input satisfies 3.9:

$r\leq\ell_{0}(\epsilon,\gamma,\delta)+O\left(\left(\log\frac{1}{\gamma}\cdot\log^{4}\frac{1}{\eta}+\log\frac{1}{\gamma}\cdot\log^{2}\frac{1}{\eta}\cdot\log\frac{1}{\alpha}\right)\cdot\log\left(\log\frac{1}{\eta}\cdot\log\frac{1}{\gamma}\cdot\log\frac{1}{\alpha}\right)\right).$

This proves Item 2 in Lemma 3.11.

###  7.3 Accuracy of estimation (Proof of Lemma 3.10)

We prove Lemma 3.10, which guarantees the accuracy of the estimation of the
probability

$P\triangleq\Pr_{\bm{{X}}\sim\mu_{I}}[\,\bm{{X}}\text{ avoids }A_{\lambda}\,]$

from the local information.

We first prove the following technical lemma, which follows directly from
Definition 3.1.

######  Lemma 7.7.

Let $I=(\\{X_{i}\\}_{i\in U}$, $\\{A_{v}\\}_{v\in V})$ be a LLL instance. For
any $\epsilon>0$, any disjoint $S,T\subset U$ with $S\cup T\neq U$, any real
functions:

$p_{1},p_{2}:\ \Sigma_{S}\to\mathbb{R}_{\geq 0},\quad\quad\quad q_{1},q_{2}:\
\Sigma_{T}\to\mathbb{R}_{\geq 0},$

if $S$ and $T$ are $\epsilon$-correlated in $I$, it holds that

$\displaystyle\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right)$
$\displaystyle\leq(1+\epsilon)\cdot$
$\displaystyle\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right).$

###### Proof.

The lemma follows by verifying:

$\displaystyle\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right)$
$\displaystyle=$
$\displaystyle\sum_{\sigma_{1},\sigma_{2}\in\Sigma_{S},\tau_{1},\tau_{2}\in\Sigma_{T}}p_{1}(\sigma_{1})\cdot
q_{1}(\tau_{1})\cdot p_{2}(\sigma_{2})\cdot
q_{2}(\tau_{2})\cdot\nu\left(\Omega_{I}^{\sigma_{1}\wedge\tau_{1}}\right)\cdot\nu\left(\Omega_{I}^{\sigma_{2}\wedge\tau_{2}}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{\sigma_{1},\sigma_{2}\in\Sigma_{S},\tau_{1},\tau_{2}\in\Sigma_{T}}p_{1}(\sigma_{1})\cdot
q_{1}(\tau_{1})\cdot p_{2}(\sigma_{2})\cdot
q_{2}(\tau_{2})\cdot(1+\epsilon)\cdot\nu\left(\Omega_{I}^{\sigma_{1}\wedge\tau_{2}}\right)\cdot\nu\left(\Omega_{I}^{\sigma_{2}\wedge\tau_{1}}\right)$
$\displaystyle\leq$
$\displaystyle(1+\epsilon)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I}^{\sigma\wedge\tau}\right).\qed$

Now we can prove Lemma 3.10.

###### Proof of Lemma 3.10.

For any $\sigma\in\Sigma_{\mathsf{vbl}(\Lambda)}$, define

$\phi(\sigma)\triangleq\begin{cases}1&\text{$\sigma$ avoids the bad event
$A_{\lambda}$, }\\\ 0&\text{$\sigma$ does not avoid the bad event
$A_{\lambda}$. }\end{cases}$

For any $v\in V$, $\mathsf{vbl}(v)\subseteq W\subseteq V$,
$\sigma\in\Sigma_{W}$, define

$\phi_{v}(\sigma)\triangleq\begin{cases}1&\text{$\sigma$ avoids the bad event
$A_{v}$, }\\\ 0&\text{$\sigma$ does not avoid the bad event $A_{v}$.
}\end{cases}$

Let $S=\mathsf{vbl}(\Lambda)$ and
$T=U\setminus\mathsf{vbl}(B_{\ell}(\Lambda))$. For any $\sigma\in\Sigma_{S}$,
define

$p_{1}(\sigma)\triangleq\prod_{\mathsf{vbl}(v)\subseteq
S}\phi_{v}(\sigma),\quad p_{2}(\sigma)\triangleq
p_{1}(\sigma)\cdot\phi(\sigma).$

For any $\tau\in\Sigma_{T}$, define

$q_{1}(\tau)\triangleq\prod_{\mathsf{vbl}(v)\subseteq T}\phi_{v}(\tau),\quad
q_{2}(\tau)\triangleq 1.$

We considered a new bad event $A_{w}$ constructed by Lemma 3.1 and a augmented
LLL instance $I_{w}$:

$A_{w}\triangleq
A^{{I}}_{\bm{\lambda}({\Lambda},{\epsilon^{k},\alpha_{2},\alpha_{1}\cdot\epsilon^{k}})},\text{
where }w\not\in V,\quad\text{ and }\quad I_{w}=(\\{X_{i}\\}_{i\in
U},\\{A_{v}\\}_{v\in V\cup\\{w\\}}).$

According to Lemma 3.1, we have $S$ and $T$ are $\epsilon^{k}$-correlated in
LLL instance $I_{w}$. By Lemma 7.7, we have

$\displaystyle\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)$ (15)
$\displaystyle\leq(1+\epsilon^{k})\cdot$
$\displaystyle\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)\cdot\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right).$

Let

$P\triangleq\Pr_{\bm{{X}}\sim\mu_{I}}[\text{ $\bm{{X}}$ avoids $A_{\lambda}$
}],\quad\text{ and }\quad P_{w}\triangleq\Pr_{\bm{{X}}\sim\mu_{I_{w}}}[\text{
$\bm{{X}}$ avoids $A_{\lambda}$}].$

It holds that

$P_{w}=\frac{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)}{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)}.$

Then, define

$\hat{P}\triangleq\frac{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)}{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)}.$

The above $P_{w}$ and $\hat{P}$ are well-defined, since their denominators are
non-zero, i.e.

$\displaystyle\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{2}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)$
$\displaystyle\geq\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(\sigma)\cdot
q_{1}(\tau)\cdot\nu\left(\Omega_{I_{w}}^{\sigma\wedge\tau}\right)$
$\displaystyle=\nu(\Omega_{I_{w}})\geq\alpha_{2}-\alpha_{1}\cdot\epsilon^{k}>0.$

Obviously, the value of $\hat{P}$ can be determined by $\Lambda$,
$A_{\lambda}$ and $I(B_{\ell+1}(\Lambda))$. By Equation 15 and simply swap the
definition of $q_{1}$ with $q_{2}$, we directly have

$\displaystyle\hat{P}\leq\left(1+\epsilon^{k}\right)\cdot
P_{w}\leq\left(1+\epsilon^{k}\right)^{2}\cdot\hat{P}.$ (16)

Now we try to estimate the difference between $P$ and $P_{w}$. First, we have

$\displaystyle P$
$\displaystyle=\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot\nu(\Omega^{\sigma}_{I})}{\nu\left(\Omega_{I}\right)}\leq\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot(\nu(\Omega^{\sigma}_{I_{w}})+\nu(A_{w})\cdot\nu_{S}(\sigma))}{\nu(\Omega_{I})}$
(17)
$\displaystyle\leq\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot\nu(\Omega^{\sigma}_{I_{w}})}{\nu(\Omega_{I_{w}})}+\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot\nu(A_{w})\cdot\nu_{S}(\sigma)}{\nu(\Omega_{I})}\leq
P_{w}+\frac{\alpha_{1}\cdot\epsilon^{k}}{\alpha_{1}}=P_{w}+\epsilon^{k}.$

On the other hand, we have

$\displaystyle P$
$\displaystyle=\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot\nu(\Omega^{\sigma}_{I})}{\nu(\Omega_{I})}\geq\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot\nu(\Omega^{\sigma}_{I_{w}})}{\nu(\Omega_{I_{w}})}\cdot\frac{\nu(\Omega_{I_{w}})}{\nu(\Omega_{I})}$
(18)
$\displaystyle\geq\frac{\sum_{\sigma\in\Sigma_{S}}p_{2}(\sigma)\cdot\nu(\Omega^{\sigma}_{I_{w}})}{\nu(\Omega_{I_{w}})}\cdot\frac{\nu(\Omega_{I})-\nu(A_{w})}{\nu(\Omega_{I})}\geq
P_{w}\cdot\left(1-\frac{\alpha_{1}\cdot\epsilon^{k}}{\alpha_{1}}\right)=P_{w}\cdot(1-\epsilon^{k}).$

By combining (16) (17) (18), we have

$\hat{P}-2\epsilon^{k}\leq P\leq\hat{P}+2\epsilon^{k}.\qed$

###  7.4 Analysis of _Substituting_ (Proof of Lemma 3.12)

We prove Lemma 3.12, which guarantees the soundness of the substituting trick.
We first construct the new random variable $X_{\beta}$ and bad event
$A_{\kappa}$, and then prove the identity stated in Lemma 3.12.

#### The construction of $X_{\beta}$.

We construct a new random variable $X_{\beta}$ follows a distribution
$\nu_{\beta}$ over a domain $\Sigma_{\beta}$. Here is the construction of
$\Sigma{\beta}$ and $\nu_{\beta}$ .

  * •

The domain $\Sigma_{\beta}$. Let
$R=\mathsf{vbl}(B_{\ell+1}(\Lambda))\setminus\mathsf{vbl}(B_{\ell}(\Lambda))$.
We set $\Sigma_{\beta}=\Sigma_{R}$.

  * •

The distribution $\nu_{\beta}$. Let $S=\mathsf{vbl}(\Lambda)$ and
$T=U\setminus\mathsf{vbl}(B_{\ell}(\Lambda))$. Let
$\omega\in\Sigma_{T\setminus R}$ be an arbitrary configuration. For any
$\pi\in\Sigma_{\beta}$, define

$P(\pi)\triangleq\frac{\nu\left(\Omega_{\hat{I}}^{\omega\wedge\pi\wedge\sigma}\right)}{\nu_{T}(\omega\wedge\pi)\cdot\nu_{S}(\sigma)}.$

Note that $P(\pi)$ does not depend on $\omega$. Order all the configurations
$\pi\in\Sigma_{\beta}$ increasingly by $P(\pi)$ as
$\pi_{1},\pi_{2},...,\pi_{|\Sigma_{\beta}|}$. Then, for $1\leq
i\leq|\Sigma_{\beta}|$, we set

$\nu_{\beta}(\pi_{i})=\begin{cases}\frac{P\left(\pi_{1}\right)}{P\left(\pi_{|\Sigma_{\beta}|}\right)}&i=1,\\\
\frac{P\left(\pi_{i}\right)-P\left(\pi_{i-1}\right)}{P\left(\pi_{|\Sigma_{\beta}|}\right)}&1<i\leq|\Sigma_{\beta}|.\end{cases}$

#### The construction of $A_{\kappa}$.

We construct the new bad event $A_{\kappa}$ as follow. The event $A_{\kappa}$
is defined on the variables in $\mathsf{vbl}(\kappa)\triangleq
R\cup\\{\beta\\}$ such that for any $\tau\in\Sigma_{\mathsf{vbl}(\kappa)}$,

$A_{\kappa}\text{ occurs if and only if }P(\tau_{R})<P(\tau_{\beta}).$

###### Proof of Lemma 3.12.

We prove the claimed properties one by one.

To prove Item 1 in Lemma 3.12, it is easy to verify that the constructions of
$X_{\beta}$ and $A_{\kappa}$ depend only on the specifications of $\Lambda$,
$\sigma$, $(\epsilon,\gamma,\delta)$ and $I(B_{\ell+1}(\Lambda))$.

Next, we prove Item 2 in Lemma 3.12. Fix any $W\subseteq T$ and its complement
$\overline{W}=T\setminus W$. Define the following set of assignments:

$\Sigma_{\overline{W}}^{\prime}\triangleq\\{\overline{w}\in\Sigma_{\overline{W}}\mid\text{$\overline{\omega}\wedge\omega$
avoids all the bad events $A_{v}$ such that $\mathsf{vbl}(v)\subseteq T$ and
$\mathsf{vbl}(v)\nsubseteq W$}\\}.$

Let
$U_{\sigma}\triangleq(U\setminus\mathsf{vbl}(B_{\ell}(\Lambda)))\cup\\{\beta\\}$.
For any $\omega\in\Sigma_{W}$ and $\overline{\omega}\in\Sigma_{\overline{W}}$,
it holds that

$\mu^{\omega\wedge\sigma}_{\hat{I},\overline{W}}(\overline{\omega})=\begin{cases}\frac{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)}{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega}\right)}&\text{if
$\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega}\right)>0$ and
$\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}$ },\\\ 0&\text{otherwise.
}\\\ \end{cases}$

and

$\mu^{\omega}_{I_{\sigma},\overline{W}}(\overline{\omega})=\begin{cases}\frac{\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega\wedge\overline{\omega}}\right)}{\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega}\right)}&\text{if
$\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega}\right)>0$ and
$\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}$},\\\
0&\text{otherwise}.\par\end{cases}$

We consider following cases:

  * •

Case 1: $\overline{\omega}\notin\Sigma_{\overline{W}}^{\prime}$. In this case,
it holds that
$\mu^{\omega\wedge\sigma}_{\hat{I},\overline{W}}(\overline{\omega})=\mu^{\omega}_{I_{\sigma},\overline{W}}(\overline{\omega})=0$.

  * •

Case 2: $\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}$ and
$\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega}\right)=0$. In this case, we
have

$\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega}\right)=\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega\wedge\overline{\omega}}\right)=\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)=\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega}\right)=0.$

Therefore, it holds that
$\mu^{\omega\wedge\sigma}_{\hat{I},\overline{W}}(\overline{\omega})=\mu^{\omega}_{I_{\sigma},\overline{W}}(\overline{\omega})=0$.

  * •

Case 3: $\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}$ and
$\nu\left(\Omega_{I_{\sigma}}^{\omega}\right)>0$. In this case, it holds that

$\mu^{\omega\wedge\sigma}_{\hat{I},\overline{W}}(\overline{\omega})=\frac{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)}{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega}\right)}=\frac{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)}{\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)}$

and

$\displaystyle\mu^{\omega}_{I_{\sigma},\overline{W}}(\overline{\omega})$
$\displaystyle=\frac{\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega\wedge\overline{\omega}}\right)}{\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega}\right)}=\frac{\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega\wedge\overline{\omega}}\right)}{\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu_{U_{\sigma}}\left(\Omega_{I_{\sigma}}^{\omega\wedge\overline{\omega}}\right)}=\frac{\nu_{T}(\omega\wedge\overline{\omega})\cdot\nu_{\beta}((\omega\wedge\overline{\omega})_{R})}{\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu_{T}(\omega\wedge\overline{\omega})\cdot\nu_{\beta}((\omega\wedge\overline{\omega})_{R})}$
$\displaystyle=\frac{\nu_{T}(\omega\wedge\overline{\omega})\cdot
P((\omega\wedge\overline{\omega})_{R})}{\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu_{T}(\omega\wedge\overline{\omega})\cdot
P((\omega\wedge\overline{\omega})_{R})}=\frac{\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)}{\sum_{\overline{\omega}\in\Sigma_{\overline{W}}^{\prime}}\nu\left(\Omega_{\hat{I}}^{\sigma\wedge\omega\wedge\overline{\omega}}\right)}$

Thus, we have
$\mu^{\omega\wedge\sigma}_{\hat{I},\overline{W}}(\overline{\omega})=\mu^{\omega}_{I_{\sigma},\overline{W}}(\overline{\omega})$.

Combing three cases,we prove that

$\forall\omega\in\Sigma_{W},\overline{\omega}\in\Sigma_{\overline{W}}:\quad\mu^{\omega\wedge\sigma}_{\hat{I},\overline{W}}(\overline{\omega})=\mu^{\omega}_{I_{\sigma},\overline{W}}(\overline{\omega}).$

At last, we prove Item 3 in Lemma 3.12. As before, for any $v\in V$,
$\omega\in\Sigma_{W}$, where $\mathsf{vbl}(v)\subseteq W\subseteq V$, let
$\phi_{v}(\omega)$ indicate whether $\omega$ avoids $A_{v}$. Let
$S=\mathsf{vbl}(\Lambda)$ and $T=U\setminus\mathsf{vbl}(B_{\ell}(\Lambda))$.
For any $x\in\Sigma_{S}$, define

$p_{1}(x)\triangleq\prod_{\mathsf{vbl}(v)\subseteq S}\phi_{v}(x)\quad\text{
and }\quad p_{2}(x)\triangleq\begin{cases}\frac{1}{\nu_{S}(x)}&x=\sigma,\\\
0&x\neq\sigma.\end{cases}$

For any $y\in\Sigma_{T}$, define

$q_{1}(y)\triangleq\prod_{\mathsf{vbl}(v)\subseteq T}\phi_{v}(y)\quad\text{
and }\quad
q_{2}(y)\triangleq\begin{cases}\frac{1}{\nu_{T}(y)}&y_{R}=\pi_{|\Sigma_{\beta}|},\\\
0&y_{R}\neq\pi_{|\Sigma_{\beta}|}.\end{cases}$

It holds that

$\displaystyle\nu_{U_{\sigma}}(\Omega_{I_{\sigma}})$
$\displaystyle=\sum_{\tau\in\Sigma_{T}}\nu_{T}(\tau)\cdot
q_{1}(\tau)\cdot\frac{P(\tau_{R})}{P(\pi_{|\Sigma_{\beta}|})}=\frac{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(x)\cdot
q_{1}(y)\cdot\nu(\Omega_{\hat{I}}^{\sigma\wedge\tau})}{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{2}(x)\cdot
q_{2}(y)\cdot\nu(\Omega_{\hat{I}}^{\sigma\wedge\tau})}.$

and

$\displaystyle\nu(\Omega_{\hat{I}})$
$\displaystyle\leq\frac{\nu_{U}(\Omega_{\hat{I}})}{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(x)\cdot
q_{2}(y)\cdot\nu(\Omega_{\hat{I}}^{\sigma\wedge\tau})}=\frac{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(x)\cdot
q_{1}(y)\cdot\nu(\Omega_{\hat{I}}^{\sigma\wedge\tau})}{\sum_{\sigma\in\Sigma_{S},\tau\in\Sigma_{T}}p_{1}(x)\cdot
q_{2}(y)\cdot\nu(\Omega_{\hat{I}}^{\sigma\wedge\tau})}.$

By Lemma 7.7, we have
$\nu_{U}(\Omega_{\hat{I}})\leq(1+\epsilon)\cdot\nu_{U_{\sigma}}(\Omega_{I_{\sigma}})$,
which implies
$\nu_{U_{\sigma}}(\Omega_{I_{\sigma}})\geq(1-\epsilon)\cdot\nu_{U}(\Omega_{\hat{I}})$.
Recall that the original LLL instance $I$ is $\alpha$-satisfiable and the
additional bad event occurs with probability no more that $\delta$. Therefore,
the LLL instance $I_{\sigma}$ is at least
$(1-\epsilon)(\alpha-\delta)$-satisfiable. ∎

###  7.5 Wrapping up the analysis of _Resampling_ (Proof of Lemma 3.13)

At last, we wrap up the analysis of the _Resampling_ phase, and prove Lemma
3.13.

###### Proof of Item 1 of Lemma 3.13.

Denote by $v_{1},v_{2},...,v_{n}$ the sequence of nodes obtained by sorting
$V$ in ascending order according to IDs. For $1\leq k\leq n$, denote by
$\bm{\mathcal{{B}}}_{k}$ the ball associated to node $v_{k}$, i.e.

$\bm{\mathcal{{B}}}_{k}\triangleq\begin{cases}B_{r_{v_{k}}}(p_{v_{k}})&\text{if
}v_{k}\in\bm{\mathcal{{R}}}\text{ and
}p_{v_{k}},r_{v_{k}}\not\in\\{\perp\\},\\\
\emptyset&\text{otherwise.}\end{cases}$

Fix arbitrary $B_{1},B_{2},...,B_{n}\subseteq V$ and assignments
$\sigma_{1}\in\Sigma_{\mathsf{vbl}(B_{1})},\sigma_{2}\in\Sigma_{\mathsf{vbl}(B_{2})}$,
…, $\sigma_{n}\in\Sigma_{\mathsf{vbl}(B_{n})}$ satisfying

$\Pr\left[\left(\bigwedge_{k=1}^{n}\bm{\mathcal{{B}}}_{k}=B_{k}\right)\wedge\left(\bigwedge_{k=1}^{n}Y_{\mathsf{vbl}(B_{k})}=\sigma_{k}\right)\right]>0.$

Assume that the input $\bm{{Y}}$ and $p_{v},r_{v}$ for
$v\in\bm{\mathcal{{R}}}$ satisfy the properties guaranteed by Lemma 3.7. Our
goal is to show that conditioned on $\bm{\mathcal{{B}}}_{k}=B_{k}$ and
$Y_{\mathsf{vbl}(B_{k})}=\sigma_{k}$ for all $1\leq k\leq n$, right after
Algorithm 3 being sequentially executed on all nodes in $\bm{\mathcal{{R}}}$,
the output assignment $\bm{{Y}}$ follows the distribution $\mu_{I}$.

For $0\leq k\leq n$, let $\vec{Y}^{(k)}$ denote the random assignment
$\vec{Y}$ right after Algorithm 3 terminates on all the active nodes $v_{j}$
with $j\leq k$. For $0\leq k\leq n$, define

$N_{k}\triangleq\\{j\mid k<j\leq n\land B_{j}\neq\emptyset\\}.$

In the rest of the proof, we show that $(\bm{{Y}}^{(k)},\\{B_{i}\\}_{i\in
N_{k}})$ satisfies the clustered conditional Gibbs property on $I$ with
parameter $(\epsilon_{0},\gamma_{0},\delta_{0})$ for any $0\leq k\leq n$. In
particular, this guarantees that $(\bm{{Y}}^{(n)},\emptyset)$ satisfies the
clustered conditional Gibbs property, which implies that the final output
$\bm{{Y}}^{(n)}$ follows the distribution $\mu_{I}$.

For $k\in N_{0}$, let $A_{\lambda_{k}}\triangleq
A^{{I}}_{\bm{\lambda}({B_{k}},{\epsilon_{0},\gamma_{0},\delta_{0}})}$. For
$0\leq k\leq n$, define

$\displaystyle\overline{U}^{(k)}\triangleq U\setminus\bigcup_{j\in
N_{k}}\mathsf{vbl}(B_{\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})}(B_{j})),\quad\text{and}\quad\overline{I}^{(k)}\triangleq\left(\\{X_{i}\\}_{i\in
U},\\{A_{v}\\}_{v\in V}\cup\\{A_{\lambda_{j}}\\}_{j\in N_{k}}\right).$

The goal is to prove that $Y^{(k)}_{\overline{U}^{(k)}}$ follows the
distribution $\mu^{\bigwedge_{j\in
N_{k}}\sigma_{j}}_{\overline{I}^{(k)},\overline{U}^{(k)}}$ for every $0\leq
k\leq n$.

We prove this by induction on $k$. As guaranteed by Lemma 3.7,
$(\bm{{Y}}^{(0)},\\{B_{i}\\}_{i\in N_{0}})$ satisfies the clustered
conditional Gibbs property on $I$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$. This becomes the basis of the
induction.

Then, we consider the general case. By induction hypothesis, assume that
$(\bm{{Y}}^{(k-1)},\\{B_{i}\\}_{i\in N_{k-1}})$ satisfy the clustered
conditional Gibbs property on $I$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$ for all $1\leq k\leq n$. This implies

$\displaystyle Y^{(k-1)}_{\overline{U}^{(k-1)}}\sim\mu^{\bigwedge_{j\in
N_{k-1}}\sigma_{j}}_{\overline{I}^{(k-1)},\overline{U}^{(k-1)}}\text{ for all
}1\leq k\leq n.$ (19)

If $B_{k}=\emptyset$, then $(\bm{{Y}}^{(k)},\\{B_{i}\\}_{i\in
N_{k}})=(\bm{{Y}}^{(k-1)},\\{B_{i}\\}_{i\in N_{k-1}})$ and the induction
follows directly. If $B_{k}\neq\emptyset$, then $v_{k}$ must be an active node
in $\bm{\mathcal{{R}}}$ on which Algorithm 3 is executed. We first verify that
the input to Algorithm 3 of Algorithm 3 executed on $v_{k}$, denoted by
$(\bm{{Y}}^{\prime};I^{\prime},B_{k},\epsilon_{0},\gamma_{0},\delta_{0},\gamma_{0})$,
satisfies 3.9.

For $j\in N_{0}$, let $X_{\beta_{j}}$ and $A_{\kappa_{j}}$ denote the
respective random variable and bad event constructed in Lemma 3.12 under
parameter $B_{j}$, $\sigma_{j}$, $(\epsilon_{0},\gamma_{0},\delta_{0})$,
$I(B_{\ell(\epsilon_{0},\gamma_{0},\delta_{0})+1}(B_{j}))$.

For $0\leq s\leq t\leq n$, define

$\displaystyle U^{(s,t)}\triangleq U\setminus\bigcup_{i\in N_{s}\setminus
N_{t}}\mathsf{vbl}(B_{\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})}(B_{i})),$
$\displaystyle V^{(s,t)}\triangleq V\setminus\bigcup_{i\in N_{s}\setminus
N_{t}}B_{\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})+1}(B_{i}),$
$\displaystyle I^{(s,t)}\triangleq\left(\\{X_{i}\\}_{i\in
U^{(s,t)}}\cup\\{X_{\beta_{i}}\\}_{i\in N_{s}\setminus
N_{t}},\\{A_{v}\\}_{v\in V^{(s,t)}}\cup\\{A_{\kappa_{i}}\\}_{i\in
N_{s}\setminus N_{t}}\right).$

Observe that $I^{(s,s)}=I$ for all $0\leq s\leq n$. Observe that, for $0\leq
s<t\leq n$, if $B_{t}=\emptyset$, then $I^{(s,t)}=I^{(s,t-1)}$. And if
$B_{t}\neq\emptyset$, then $I^{(s,t)}$ is obtained from $I^{(s,t-1)}$ by
substituting the ball
$B_{\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})+1}(B_{t})$ with
$A_{\lambda_{t}}$ and substituting
$\mathsf{vbl}(B_{\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})}(B_{t}))$ with
$X_{\beta_{t}}$. According to Lemma 3.7, for any distinct $i,j\in N_{0}$, the
distance between $B_{i}$ and $B_{j}$ is at least
$2(\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})+2)$. One can verify that
$I^{(k,n)}=I^{\prime}$.

For $k\leq j\leq n$, define

$\bm{{Y}}^{(k,j)}\triangleq
Y^{(k-1)}_{U^{(k,j)}}\wedge(Y^{\prime}_{\beta_{j}})_{j\in N_{k}\setminus
N_{j}}.$

One can verify that $\bm{{Y}}^{(k,n)}=\bm{{Y}}^{\prime}$.

Then, we verify that the input of _RecursiveSampling_
$(\bm{{Y}}^{\prime};I^{\prime},B_{k},\epsilon_{0},\gamma_{0},\delta_{0},\gamma_{0})$
satisfies 3.9. The first property can be verified easily. For the second
property, according to Lemma 3.12, it holds that
$\nu(\Omega_{I^{(k,j)}})\geq(1-\epsilon_{0})(\nu(\Omega_{I^{(k,j-1)}})-\delta_{0})$
for all $k<j\leq n$. Note that the LLL instance $I^{(k,k)}$ is the original
LLL instance $I$, which is $\gamma$-satisfiable. Thus, it holds that

$\displaystyle\nu(\Omega_{I^{(k,n)}})$
$\displaystyle\geq(1-\epsilon_{0})^{n}\cdot\nu(\Omega_{I^{(k,k)}})-n\cdot\delta_{0}$
$\displaystyle\geq\left(1-\frac{1}{2n}\right)^{n}\nu(\Omega_{I^{(k,k)}})-n\cdot\frac{\zeta_{0}\cdot\gamma}{24n^{3}}\geq\frac{\gamma}{8}\geq\gamma_{0},$

which means that $I^{(k,n)}(V\setminus B_{k})$ is also
$\gamma_{0}$-satisfiable. It remains to verify the third property, which
states that the $(\bm{{Y}}^{(k,n)},\\{B_{k}\\})$ satisfies the clustered
conditional Gibbs property on instance $I^{(k,n)}$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$. This is proved by the following claim.

######  Claim 7.8.

For $k\leq j\leq n$, it holds that
$(\bm{{Y}}^{(k,j)},\\{B_{k}\\}\cup\\{B_{i}\\}_{i\in N_{j}})$ satisfies the
clustered conditional Gibbs property on $I^{(k,j)}$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$.

###### Proof.

For $k\leq j\leq n$, define

$\displaystyle\hat{U}^{(k,j)}\triangleq U^{(k-1,n)}\cup\\{\beta_{i}\\}_{i\in
N_{k}\setminus N_{j}},$
$\displaystyle\hat{I}^{(k,j)}\triangleq\left(\\{X_{i}\\}_{i\in
U^{(k,j)}}\cup\\{X_{\beta_{i}}\\}_{i\in N_{k}\setminus
N_{j}},\\{A_{v}\\}_{v\in V^{(k,j)}}\cup\\{A_{\kappa_{i}}\\}_{i\in
N_{k}\setminus N_{j}}\cup\\{A_{\lambda_{i}}\\}_{i\in\\{k\\}\cup
N_{j}}\right).$

The goal is to prove that $Y^{(k,j)}_{\hat{U}^{(k,j)}}$ follows the
distribution $\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j}}\sigma_{i}}_{\hat{I}^{(k,j)},\hat{U}^{(k,j)}}$ for $k\leq j\leq n$.

This is proved by induction on $j$. For the induction basis, assuming $j=k$,
in this case we have $(\bm{{Y}}^{(k,k)},\\{B_{k}\\}\cup\\{B_{i}\\}_{i\in
N_{k}})=(\bm{{Y}}^{(k-1)},\\{B_{i}\\}_{i\in N_{k-1}})$ and $I^{(k,k)}=I$. By
(19), we have

$Y^{(k,k)}_{\overline{U}^{(k-1)}}\sim\mu^{\bigwedge_{i\in
N_{k-1}}\sigma_{i}}_{\overline{I}^{(k-1)},U^{(k-1)}}.$

Observe that $U^{(k-1,n)}=\hat{U}^{(k,k)}$, $\left(\bigwedge_{i\in
N_{k-1}}\sigma_{i}\right)=\left(\sigma_{k}\wedge\bigwedge_{i\in
N_{k}}\sigma_{i}\right)$ and $\overline{I}^{(k-1)}=\hat{I}^{(k,k)}$. It holds
that

$Y^{(k,k)}_{\hat{U}^{(k,k)}}\sim\mu^{\sigma_{k}\wedge\bigwedge_{j\in
N_{k}}\sigma_{j}}_{\hat{I}^{(k,k)},\hat{U}^{(k,k)}}.$

Next, consider the general case. By induction hypothesis, for $j-1$ for
$k<j\leq n$, the clustered conditional Gibbs property is satisfied by
$(\bm{{Y}}^{(k,j-1)},\\{B_{k}\\}\cup\\{B_{i}\\}_{i\in N_{j-1}})$ on
$I^{(k,j-1)}$ with parameter $(\epsilon_{0},\gamma_{0},\delta_{0})$, which
means

$\displaystyle
Y^{(k,j-1)}_{\hat{U}^{(k,j-1)}}\sim\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j-1}}\sigma_{i}}_{\hat{I}^{(k,j-1)},\hat{U}^{(k,j-1)}}.$ (20)

Depending on whether $B_{j}=\emptyset$, there are two cases. First, if $B_{j}$
is $\emptyset$, then $(\bm{{Y}}^{(k,j)},\\{B_{k}\\}\cup\\{B_{i}\\}_{i\in
N_{j}})=(\bm{{Y}}^{(k,j-1)},\\{B_{k}\\}\cup\\{B_{i}\\}_{i\in N_{j-1}})$ and
$I^{(k,j)}=I^{(k,j-1)}$. By (20), it holds that

$Y^{(k,j)}_{\hat{U}^{(k,j)}}\sim\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j}}\sigma_{i}}_{\hat{I}^{(k,j)},\hat{U}^{(k,j)}}.$

Next, assume $B_{j}\neq\emptyset$. By Lemma 3.12, for any
$\tau\in\Sigma_{\hat{U}^{(k,j-1)}}$,

$\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j-1}}\sigma_{i}}_{\hat{I}^{(k,j-1)},\hat{U}^{(k,j-1)}}(\tau)=\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j}}\sigma_{i}}_{\hat{I}^{(k,j)},\hat{U}^{(k,j-1)}}(\tau).$

Note that $Y^{(k,j-1)}_{\hat{U}^{(k,j-1)}}=Y^{(k,j)}_{\hat{U}^{(k,j-1)}}$. By
(20), we have

$Y^{(k,j)}_{\hat{U}^{(k,j-1)}}\sim\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j}}\sigma_{i}}_{\hat{I}^{(k,j)},\hat{U}^{(k,j-1)}}.$

Recall that each $Y^{(k,j)}_{\beta_{j}}$ is drawn independent from the
distribution
$\mu^{Y^{(k-1)}_{\mathsf{vbl}(\kappa_{j})\setminus\\{\beta_{j}\\}}}_{I^{(k,n)},\beta_{j}}$.
By Lemma 3.7, for any distinct $i,j\in N_{0}$, the distance between $B_{i}$
and $B_{j}$ is at least $2(\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})+2)$.
Thus, we have
$Y^{(k-1)}_{\mathsf{vbl}(\kappa_{j})\setminus\\{\beta_{j}\\}}=Y^{(k,j)}_{\mathsf{vbl}(\kappa_{j})\setminus\\{\beta_{j}\\}}$
and for any $c\in\Sigma_{\beta_{j}}$,

$\mu^{Y^{(k-1)}_{\mathsf{vbl}(\kappa_{j})\setminus\\{\beta_{j}\\}}}_{I^{(k,n)},\beta_{j}}(c)=\mu^{Y^{(k,j)}_{\mathsf{vbl}(\kappa_{j})\setminus\\{\beta_{j}\\}}}_{\hat{I}^{(k,j)},\beta_{j}}(c).$

It then holds that for any $\tau\in\Sigma_{\hat{U}^{(k,j)}}$,

$\displaystyle\Pr\left(Y^{(k,j)}_{\hat{U}^{(k,j)}}=\tau\right)$
$\displaystyle=\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j}}\sigma_{i}}_{\hat{I}^{(k,j)},\hat{U}^{(k,j-1)}}(\tau_{\hat{U}^{(k,j-1)}})\cdot\mu^{\tau_{\mathsf{vbl}(\kappa_{j})\setminus\\{\beta_{j}\\}}}_{\hat{I}^{(k,j)},\beta_{j}}(\tau_{\beta_{j}})$
$\displaystyle=\mu^{\sigma_{k}\wedge\bigwedge_{i\in
N_{j}}\sigma_{i}}_{\hat{I}^{(k,j)},\hat{U}^{(k,j)}}(\tau).$

This proves that $(\bm{{Y}}^{(k,j)},\\{B_{k}\\}\cup\\{B_{i}\\}_{i\in N_{j}})$
satisfies the clustered conditional Gibbs property on instance $I^{(k,j)}$
with parameter $(\epsilon_{0},\delta_{0},\gamma_{0})$. ∎

By 7.8, we have that $(\bm{{Y}}^{(k,n)},\\{B_{k}\\})$ satisfies the clustered
conditional Gibbs property on $I^{(k,n)}$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$. Thus, upon the execution of Algorithm
3 on $v_{k}$, the input to Algorithm 3 satisfies 3.9. By Lemma 3.11, after the
execution of Algorithm 3 of Algorithm 3, $\bm{{Y}}^{(k,n)}$ follows the
distribution $\mu_{I^{(k,n)}}$. Thus, it holds that $Y^{(k,n)}_{U^{(k,n)}}$ is
identical to $Y^{(k)}_{U^{(k,n)}}$ and follows the distribution
$\mu_{I^{(k,n)},U^{(k,n)}}$.

For $k\leq j\leq n$, define

$\displaystyle\overline{I}^{(k,j)}\triangleq\left(\\{X_{i}\\}_{i\in
U^{(k,j)}}\cup\\{X_{\beta_{i}}\\}_{i\in N_{k}\setminus
N_{j}},\\{A_{v}\\}_{v\in V^{(k,j)}}\cup\\{A_{\lambda_{i}}\\}_{i\in
N_{k}\setminus N_{j}}\cup\\{A_{\kappa_{i}}\\}_{i\in N_{j}}\right).$

By Lemma 3.12, for any $\pi\in\Sigma_{U^{(k,n)}}$, it holds that

$\mu_{I^{(k,n)},U^{(k,n)}}(\pi)=\mu_{\bar{I}^{(k,n-1)},U^{(k,n)}}^{\bigwedge_{i\in
N_{n-1}}\sigma_{i}}(\pi)=\mu_{\bar{I}^{(k,n-2)},U^{(k,n)}}^{\bigwedge_{i\in
N_{n-2}}\sigma_{i}}(\pi)=...=\mu_{\bar{I}^{(k,k)},U^{(k,n)}}^{\bigwedge_{i\in
N_{k}}\sigma_{i}}(\pi).$

Thus, it holds that

$Y^{(k)}_{U^{(k,n)}}\sim\mu_{\bar{I}^{(k,k)},U^{(k,n)}}^{\bigwedge_{i\in
N_{k}}\sigma_{i}}(\pi).$

Recall that $U^{(k,n)}=\overline{U}^{(k)}$ and
$\overline{I}^{(k,k)}=\overline{I}^{(k)}$. It holds that
$Y^{(k)}_{\overline{U}^{(k)}}$ follows the distribution $\mu^{\bigwedge_{j\in
N_{k}}\sigma_{j}}_{\overline{I}^{(k)},\overline{U}^{(k)}}$. Thus, after
executing Algorithm 3 of Algorithm 3, we have that
$(\bm{{Y}}^{(k)},\\{B_{i}\\}_{i\in N_{k}})$ satisfies the clustered
conditional Gibbs property on instance $I$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$. This completes the induction.

Therefore, $(\vec{Y}^{(n)},\emptyset)$ satisfies the clustered conditional
Gibbs property on instance $I$ with parameter
$(\epsilon_{0},\gamma_{0},\delta_{0})$. As argued before, this guarantees that
After Algorithm 3 being sequentially executed on all node
$v\in\bm{\mathcal{{R}}}$, the final output assignment $\vec{Y}=\bm{{Y}}^{(n)}$
follows the distribution $\mu_{I}$. ∎

###### Proof of Item 2 of Lemma 3.13.

Fix any $0<\eta<1$, the follows hold.

  * •

According to Item 2 of Lemma 3.11, with probability $1-\frac{\eta}{2}$, at
every node $v\in\bm{\mathcal{{R}}}$, the call to the _RecursiveSampling_
procedure in Algorithm 3 returns within radius

$r_{1}=r_{v}+\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})+\widetilde{O}\left(\log^{4}n\cdot\left(\log\frac{1}{\gamma}\cdot\log^{4}\frac{1}{\eta}+\log^{2}\frac{1}{\gamma}\cdot\log^{2}\frac{1}{\eta}\right)\right)$

from the center $p_{v}$ in the LLL instance $I^{\prime}$. And
$I^{\prime}(B_{r_{1}}(p_{v}))$ can be locally constructed within
$I({B_{r_{2}}(v)})$, where

$r_{2}=r_{1}+O(\mathcal{D}+|\bm{\mathcal{{R}}}|\cdot\ell_{0}(\epsilon_{0},\gamma_{0},\delta_{0})).$

  * •

According to Item 3 of Lemma 3.7, with probability $1-\frac{\eta}{2}$, we have
$\mathcal{D}=\tilde{O}(|\bm{\mathcal{{R}}}|\cdot\log^{2}n\log^{2}\frac{1}{\gamma}\log\frac{1}{\eta})$,
which implies
$r_{v}=\tilde{O}(|\bm{\mathcal{{R}}}|\cdot\log^{2}n\log^{2}\frac{1}{\gamma}\log\frac{1}{\eta})$.

Overall, with probability at least $1-\eta$, Algorithm 3 returns at every node
$v\in\bm{\mathcal{{R}}}$ with radius bounded by

$\widetilde{O}\left(|\bm{\mathcal{{R}}}|\cdot\log^{2}n\cdot\log^{2}\frac{1}{\gamma}\cdot\log\frac{1}{\eta}\right)+\widetilde{O}\left(\log^{4}n\cdot\log^{2}\frac{1}{\gamma}\cdot\log^{4}\frac{1}{\eta}\right).\qed$

## References

  * AJ [22] Konrad Anand and Mark Jerrum.  Perfect sampling in infinite spin systems via strong spatial mixing.  SIAM Journal on Computing, 51(4):1280–1295, 2022.
  * Bab [79] László Babai.  Monte-carlo algorithms in graph isomorphism testing.  Université tde Montréal Technical Report, DMS, (79-10), 1979\.
  * BGG+ [19] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic.  Approximation via correlation decay when strong spatial mixing fails.  SIAM Journal on Computing, 48(2):279–349, 2019.
  * Cla [95] Kenneth L Clarkson.  Las vegas algorithms for linear and integer programming when the dimension is small.  Journal of the ACM (JACM), 42(2):488–499, 1995.
  * EL [75] Paul Erdos and László Lovász.  Problems and results on 3-chromatic hypergraphs and some related questions.  Infinite and finite sets, 10(2):609–627, 1975.
  * FGW+ [23] Weiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang, and Yitong Yin.  Towards derandomising markov chain monte carlo.  In IEEE 2023 Annual Symposium on Foundations of Computer Science (FOCS), 2023.
  * FGY [22] Weiming Feng, Heng Guo, and Yitong Yin.  Perfect sampling from spatial mixing.  Random Structures & Algorithms, 61(4):678–709, 2022.
  * FGYZ [21] Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang.  Fast sampling and counting k-sat solutions in the local lemma regime.  Journal of the ACM (JACM), 68(6):1–42, 2021.
  * FVY [21] Weiming Feng, Nisheeth K Vishnoi, and Yitong Yin.  Dynamic sampling from graphical models.  SIAM Journal on Computing, 50(2):350–381, 2021.
  * FY [18] Weiming Feng and Yitong Yin.  On local distributed sampling and counting.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 189–198, 2018.
  * GGH+ [23] Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň.  Improved distributed network decomposition, hitting sets, and spanners, via derandomization.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2532–2566. SIAM, 2023.
  * GHK [18] Mohsen Ghaffari, David G Harris, and Fabian Kuhn.  On derandomizing local distributed algorithms.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 662–673. IEEE, 2018.
  * GJL [19] Heng Guo, Mark Jerrum, and Jingcheng Liu.  Uniform sampling through the Lovász local lemma.  Journal of the ACM (JACM), 66(3):18:1–18:31, 2019.
  * GKM [17] Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus.  On the complexity of local distributed graph problems.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 784–797. ACM, 2017.
  * Har [20] David G Harris.  New bounds for the moser-tardos distribution.  Random Structures & Algorithms, 57(1):97–131, 2020.
  * HSW [21] Kun He, Xiaoming Sun, and Kewen Wu.  Perfect sampling for (atomic) lov$\backslash$’asz local lemma.  arXiv preprint arXiv:2107.03932, 2021.
  * HWY [22] Kun He, Chunyang Wang, and Yitong Yin.  Sampling lovász local lemma for general constraint satisfaction solutions in near-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 147–158. IEEE, 2022.
  * JPV [21] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong.  Towards the sampling lovász local lemma.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 173–183. IEEE, 2021.
  * JVV [86] Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani.  Random generation of combinatorial structures from a uniform distribution.  Theoret. Comput. Sci., 43:169–188, 1986.
  * Kal [92] Gil Kalai.  A subexponential randomized simplex algorithm.  In Proceedings of the twenty-fourth annual ACM Symposium on Theory of Computing (STOC), pages 475–482, 1992.
  * Lin [92] Nathan Linial.  Locality in distributed graph algorithms.  SIAM Journal on Computing (SICOMP), 21(1):193–201, 1992.
  * LS [93] Nathan Linial and Michael Saks.  Low diameter graph decompositions.  Combinatorica, 13(4):441–454, 1993.
  * LSZ [93] Michael Luby, Alistair Sinclair, and David Zuckerman.  Optimal speedup of las vegas algorithms.  Information Processing Letters, 47(4):173–180, 1993.
  * Moi [19] Ankur Moitra.  Approximate counting, the lovász local lemma, and inference in graphical models.  Journal of the ACM (JACM), 66(2):1–25, 2019.
  * MR [95] Rajeev Motwani and Prabhakar Raghavan.  Randomized algorithms.  Cambridge university press, 1995.
  * MSL [92] D Mitchell, B Selman, and H Leveque.  A new method for solving hard satisfiability problems.  In Proceedings of the tenth national conference on artificial intelligence (AAAI-92), pages 440–446, 1992.
  * MT [10] Robin A Moser and Gábor Tardos.  A constructive proof of the general Lovász local lemma.  Journal of the ACM (JACM), 57(2):11, 2010.
  * MU [05] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis.  Cambridge University Press, 2005.
  * NS [95] Moni Naor and Larry Stockmeyer.  What can be computed locally?  SIAM Journal on Computing (SICOMP), 24(6):1259–1277, 1995.
  * Pel [00] David Peleg.  Distributed computing: a locality-sensitive approach.  SIAM, 2000.
  * PW [96] James G. Propp and David B. Wilson.  Exact sampling with coupled Markov chains and applications to statistical mechanics.  Random Structures Algorithms, 9(1-2):223–252, 1996.

##  Appendix A Simulation of $\mathsf{SLOCAL}\text{-}\mathsf{LV}$ in
$\mathsf{LOCAL}$ Model

We prove Proposition 3.2. The $\mathsf{LOCAL}$ algorithm for simulating the
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm is described in Algorithm 6.
Recall that whether a node $v\in V$ is an active node (which means that $v\in
A$) is indicated in the local memory $M_{v}$. For each active node $v\in A$,
Algorithm 6 is executed on $v$, with the initial $M_{v}$ presented to the
$\mathsf{LOCAL}$ algorithm as $v$’s input. Also recall that we define $G^{t}$
to be the $t$-th power graph with an edge between any pair of $u,v$ where
$\mathrm{dist}_{G}(u,v)\leq t$.

1 initialize $A_{v}\leftarrow\emptyset$;

2 for  _$i=1$ to $\lceil\log n\rceil$_ do

3 in the induced subgraph $G^{(2^{i+1})}[A]$, find the maximal connected
component containing $v$, denoted by $A^{\prime}$;

4

5 simulate the $\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm with set
$A^{\prime}$ of active nodes, where the simulation _fails_ if the maximum
radius accessed by the $\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm exceeds
$2^{i}$;

6

7 if  _the simulation does not fail_ then

8 let $A_{v}\leftarrow A^{\prime}$ and update the output states according to
the simulation of $v$;

9 break;

10

11

12

13if  _there exists $u\in A$ with $A_{u}\subseteq A_{v}$_ then

14 cancel all the updates to output made by $u$;

// In this case, we say that $u$ is canceled by $v$.

15

16

17if  _there exists $u\in A$ with $A_{v}\subseteq A_{u}$_ then

18 cancel all the updates to output made by $v$;

// In this case, we say that $v$ is canceled by $u$.

19

Algorithm 6 The $\mathsf{LOCAL}$ algorithm for simulating
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ at active node $v\in A$

It is easy to see that Algorithm 6 terminates, and when it terminates, a set
$A_{v}\subseteq A$ is constructed for each $v\in A$. The following lemma
follows from the property of $G^{(2^{i+1})}$.

######  Lemma A.1.

For distinct $u,v\in A$, one of the followings must be true:

  1. 1.

$A_{u}\cap A_{v}=\emptyset$.

  2. 2.

$A_{u}\subseteq A_{v}$.

  3. 3.

$A_{v}\subseteq A_{u}$.

###### Proof.

Assume $A_{u}$ is a maximum connected component of $G^{t_{u}}$ and $A_{v}$ is
a maximum connected component of $G^{t_{v}}$, for some integers $t_{u}$ and
$t_{v}$. Suppose $t_{u}\leq t_{v}$. If $A_{u}\cap A_{v}\not=\emptyset$, then
in $G^{t_{v}}$, $A_{u}$ and $A_{v}$ must be in the same connected components,
since every edge in $G^{t_{u}}$ is also an edge in $G^{t_{v}}$. Thus,
$A_{u}\subseteq A_{v}$. Similarly, if $t_{u}\geq t_{v}$, then $A_{v}\subseteq
A_{u}$. ∎

The following lemma is because of the condition of canceling a vertex.

######  Lemma A.2.

For any $v\in A$, there exists $u\in A$ such that $v\in A_{u}$ and $u$ is not
canceled.

###### Proof.

Consider the last time $v$ appears in some $A_{u}$. If $v$ is not in any
$A_{u}$ in the end, $u$ must be canceled by some other vertex $u^{\prime}$, in
which case we have $A_{u}\subseteq A_{u^{\prime}}$, and hence $v\in
A_{u^{\prime}}$, a contradiction. ∎

For any $v\in A$, note that the simulation must succeed if $i=\lceil\log
n\rceil$. Thus, there exists an $i$ for $v$ such that the simulation in the
$i$-th iteration does not fail. Denote such $i$ as $I_{v}$. Suppose that this
successful simulation has the radius $\ell^{\prime}_{v,j}$ for $v\in
A^{\prime}$ in the $j$-th scan. Define $T_{v}=\cup_{v\in
A^{\prime},j\in[N]}B_{\ell^{\prime}_{v,j}}(v)$, i.e., the set of all vertices
whose outputs are supposed to be updated by $v$. The following lemmas
guarantee the correctness of the simulation.

######  Lemma A.3.

If $u,v\in A$ and both $u,v$ are not canceled, then $T_{u}\cap
T_{v}=\emptyset$.

###### Proof.

According to Lemma A.1, we have $A_{u}\cap A_{v}=\emptyset$. If $T_{u}\cap
T_{v}\not=\emptyset$, there must exist $u^{\prime}\in A_{u},v^{\prime}\in
A_{v}$ such that $B_{x}(u^{\prime})\cap B_{y}(v^{\prime})\not=\emptyset$,
where $x,y$ are the radii accessed by $u^{\prime}$ and $v^{\prime}$ and
satisfy $x\leq 2^{I_{u}},y\leq 2^{I_{v}}$. w.o.l.g, we assume $I_{u}\leq
I_{v}$. Then we have $\mathrm{dist}_{G}(u^{\prime},v^{\prime})\leq x+y\leq
2^{I_{v}+1}$. That is to say, $u^{\prime}$ and $v^{\prime}$ has an edge in
$G^{(2^{I_{v}+1})}$, which causes a contradiction since $A_{v}$ is a maximum
connected components. ∎

######  Lemma A.4 (correctness of simulation).

For any $u\in A$, if $u$ is not canceled, then Algorithm 6 at $u$ produces the
same outputs for the nodes in $A_{u}$ as in the
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm.

###### Proof.

We will prove by induction on $k$ that, the first $k$ vertices accessed by the
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm is simulated exactly the same
in our $\mathsf{LOCAL}$ algorithm by some $u\in A$. For $k=1$, According to
Lemma A.2, there exists $A_{u}$ containing the first vertex accessed in the
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm, which is simulated correctly
by $u$. Assume that the first $k$ vertices are simulated correctly. For the
$k+1$-th vertex accessed, suppose it is vertex $v$ in the $j$-th phase. By
Lemma A.2, there exists $A_{u}$ containing the $k+1$-th vertex accessed in the
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm, and it will only access
$B_{\ell_{v,j}}(v)\in T_{u}$, which only contains the information updated by
the vertices in $A_{u}$ according to Lemma A.3. Thus, the simulation is
correct. ∎

The following lemma bounds the round complexity of Algorithm 6. Recall that
$\ell_{v,j}$ is the radius of the ball accessed by the
$\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm at node $v\in A$ in the $j$-th
phase.

######  Lemma A.5.

For any $v\in A$, we have $I_{v}\leq\lceil\log\max_{v\in
A,j\in[N]}\ell_{v,j}\rceil$.

###### Proof.

Consider the $\lceil\log\max_{v\in A,j\in[N]}\ell_{v,j}\rceil$-th iteration
for vertex $v$. We claim that for any $u\in A\backslash A_{v}$, and $k\in[N]$,
we have $B_{\ell_{u,k}}\cap\left(\cup_{v\in
A^{\prime},j\in[N]}B_{\ell_{v,j}}(v)\right)=\emptyset$. Otherwise, $u$ has
distance at most $2\cdot\max_{v\in A,j\in[N]}\ell_{v,j}$ to a vertex in
$A_{v}$, contradicting the fact that $A_{v}$ is a maximal connected components
of $G^{x}$ for $x\geq 2\cdot\max_{v\in A,j\in[N]}\ell_{v,j}$. By the same
argument as in the proof of Lemma A.4, the simulation on $A_{v}$ will produce
the same output as in the $\mathsf{SLOCAL}\text{-}\mathsf{LV}$ algorithm, in
which case the simulation must not fail. ∎

Now we are ready to prove Proposition 3.2.

###### Proof of Proposition 3.2.

The correctness of Algorithm 6 follows from Lemmas A.4 and A.2.

Then we bound the complexity of Algorithm 6. Let $M=\max_{v\in
A,j\in[N]}\ell_{v,j}$. For a vertex $v\in A$, to run the $i$-th loop, $v$ need
to find the maximal connected component in $G^{2^{i}+1}[A]$, and grow a ball
of radius at most $2^{i}$ from each vertex in the connected component.
According to Lemma A.5, we have $2^{i}+1=O(M)$ since $i<I_{v}$. The maximal
connected components in $G^{O(M)}[A]$ has diameter at most $O(|A|\cdot M)$ in
$G$. Thus, $u$ only needs to collect the information in $B_{\ell}(u)$ for some
$\ell=O(|A|\cdot M)$. The only problem is that $u$ do not know $\ell$
initially. This can be solved by guessing $\ell$ by scanning
$\ell^{\prime}=2^{i}$ for $i=1,2,\ldots$, collecting information in
$B_{\ell^{\prime}}(u)$ and determining whether stops. ∎