# Fast sampling of satisfying assignments from random $k$-SAT††thanks: For the
purpose of Open Access, the authors have applied a CC BY public copyright
licence to any Author Accepted Manuscript version arising from this
submission. All data is provided in full in the results section of this paper.

Andreas Galanis  Department of Computer Science, University of Oxford, Wolfson
Building, Parks Road, Oxford, OX1 3QD, UK. Leslie Ann Goldberg 11footnotemark:
1 Heng Guo School of Informatics, University of Edinburgh, Informatics Forum,
10 Crichton Street, Edinburgh, EH8 9AB, UK. HG has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No. 947778). Andrés
Herrera-Poyatos 11footnotemark: 1 This author is supported by an Oxford-
DeepMind Graduate Scholarship and a EPSRC Doctoral Training Partnership.

(2 November 2022)

###### Abstract

We give a nearly linear-time algorithm to approximately sample satisfying
assignments in the random $k$-SAT model when the density of the formula scales
exponentially with $k$. The best previously known sampling algorithm for the
random $k$-SAT model applies when the density $\alpha=m/n$ of the formula is
less than $2^{k/300}$ and runs in time $n^{\exp(\Theta(k))}$ (Galanis,
Goldberg, Guo and Yang, SIAM J. Comput., 2021). Here $n$ is the number of
variables and $m$ is the number of clauses. Our algorithm achieves a
significantly faster running time of $n^{1+o_{k}(1)}$ and samples satisfying
assignments up to density $\alpha\leq 2^{0.039k}$.

The main challenge in our setting is the presence of many variables with
unbounded degree, which causes significant correlations within the formula and
impedes the application of relevant Markov chain methods from the bounded-
degree setting (Feng, Guo, Yin and Zhang, J. ACM, 2021; Jain, Pham and Vuong,
2021). Our main technical contribution is a $o_{k}(\log n)$ bound of the sum
of influences in the $k$-SAT model which turns out to be robust against the
presence of high-degree variables. This allows us to apply the spectral
independence framework and obtain fast mixing results of a uniform-block
Glauber dynamics on a carefully selected subset of the variables. The final
key ingredient in our method is to take advantage of the sparsity of
logarithmic-sized connected sets and the expansion properties of the random
formula, and establish relevant properties of the set of satisfying
assignments that enable the fast simulation of this Glauber dynamics.

##  1 Introduction

The random $k$-SAT model is a foundational model in the study of randomised
algorithms. For integers $k,n,m\geq 2$, the random formula $\Phi=\Phi(k,n,m)$
is a $k$-CNF formula chosen uniformly at random from the set of formulas with
$n$ Boolean variables and $m$ clauses, where each clause has $k$ literals
(repetitions allowed). Here, we consider the sparse regime where the density
of the formula, $\alpha=m/n$, is bounded by an absolute constant. An important
question is determining the probability that the random formula is satisfiable
as a function of its density (in the limit $n\rightarrow\infty$).
Interestingly, for all sufficiently large $k$, the probability that $\Phi$ is
satisfiable drops abruptly from $1$ to $0$ when the density $\alpha$ crosses a
certain threshold $\alpha_{\star}(k)$. Recently there has been tremendous
progress in establishing this phase transition, concluding that
$\alpha_{\star}(k)=2^{k}\log 2-\tfrac{1}{2}(1+\log 2)+o_{k}(1)$ as
$k\to\infty$ [16, 13]. Despite the good progress on pinning down this phase
transition, finding satisfying assignments for densities up to $\alpha^{*}$
poses severe challenges. In fact, the best known algorithm [10] for finding a
satisfying assignment of a random formula $\Phi$ succeeds up to densities
$(1+o_{k}(1))\tfrac{2^{k}}{k}\log k$, and going beyond such densities is a
major open problem with links to phase transitions [1].

Lately there has been significant interest in the related computational
problem of sampling satisfying assignments of $\Phi$ uniformly at random. This
problem is closely connected to the problem of estimating the number of
satisfying assignments of $\Phi$, also known as the value of the partition
function of the model. From a probabilistic viewpoint, the analysis of the
partition function depends on subtle properties of the solution set $\Omega$
consisting of the satisfying assignments of $\Phi$ [2, 12, 37, 33]. In this
direction, there has been substantial work on finding the so-called free
energy of the model, i.e., the asymptotic value of the quantity
$\tfrac{1}{n}\mathbf{E}[\log(1+|\Omega|)]$. Computing the $k$-SAT free energy
is a difficult problem which is still open (roughly, the difficulty comes from
the asymmetry of the model and the unbounded degrees), but there have been
results for closely related models including the permissive version of the
model [12, 33, 14], the regular $k$-SAT model [15], and the regular NAE-SAT
model [36, 37]. Very recently, a formula for the free energy of the $2$-SAT
model was given in [2].

Regarding the algorithmic problem of sampling satisfying assignments uniformly
at random, in the random $k$-SAT model progress has been slower relative to
other well-studied models on random graphs (such as $k$-colourings or
independent sets). One of the main reasons for this is that the usual
distribution properties that are typically used to obtain fast algorithms
(such as correlation decay and spatial mixing) fail to hold for densities as
low as $\alpha=o_{k}(1)$ [33]. These issues are in fact present already in the
bounded-degree $k$-SAT setting, where the formulas are worst-case but every
variable is constrained to have a bounded-number of occurrences. For random
formulas, these issues are further aggravated by the fact that the degrees of
a linear number of variables are unbounded. Very recently, [21] gave an
approximate counting algorithm (FPTAS) for the number of satisfying
assignments of $\Phi$ when $k$ is large enough and $\alpha\lesssim 2^{k/300}$
(where $\lesssim$ hides a polynomial factor in $1/k$). This algorithm elevates
Moitra’s counting method for bounded-degree $k$-SAT [32] to the random formula
setting, and is the first polynomial-time approximate-counting algorithm to
achieve an exponential-in-$k$ bound on $\alpha$. However, its running time is
$n^{\exp(\Theta(k))}$ because the algorithm repeatedly has to enumerate local
structures (including solving LPs as a subroutine), which does not scale well
with $k$. Hence, the problem of finding a _fast_ algorithm for sampling the
satisfying assignments in the random $k$-SAT model has remained open.

In this work we give a fast algorithm that in time $n^{1+o_{k}(1)}$
approximately samples satisfying assignments of a random $k$-SAT formula of
density $\alpha\leq 2^{0.039k}$, within arbitrarily small polynomial error.
Moreover, our result significantly extends the densities under consideration
compared to the previous bound $\alpha\lesssim 2^{k/300}$ from [21]. Our
algorithm first runs a Markov chain to sample assignments of a judiciously-
chosen subset of variables of $\Phi$ (from the relevant marginal
distribution), and subsequently extending this random assignment to all the
variables. This has the advantage that it avoids the enumeration of local
structures, and in fact achieves a nearly-linear running time. We give a high-
level overview of the techniques developed in our proofs in Section 2.
Roughly, our Markov chain is a uniform-block Glauber dynamics which,
interestingly, mixes quickly despite the presence of high-degree variables in
the random formula. The main point of departure from similar approaches that
have been applied to the bounded-degree setting is that we completely
circumvent sophisticated coupling arguments that have been used there and
which are unfortunately severely constricted by the unbounded degrees in our
setting (and made inapplicable). Instead, our main technical contribution is
to show that the stationary distribution of our chain is $(c^{k}\log
n)$-spectrally independent for some constant $c\in(0,1)$, allowing us to apply
recently-developed tools in the analysis of Markov chains. Unlike most
applications of spectral independence, our proof does not rely on correlation
decay (which, as we mentioned, fails to hold for densities exponential in
$k$). We show our spectral-independence bounds by relating the probabilistic
properties of the solution space with the structure of the formula using
coupling techniques, so that we can exploit local sparsity properties of
random $k$-SAT.

To formally state our main result, we say that an event $\mathcal{E}$
regarding the choice of the random formula $\Phi$ holds _with high
probability_ (abbreviated w.h.p.) if $\operatorname{Pr}(\mathcal{E})=1-o(1)$
as $n\to\infty$. The total variation distance between two probability
distributions $\mu$ and $\nu$ over the same space $\Omega$ is given by
$\tfrac{1}{2}\sum_{x\in\Omega}\lvert\mu(x)-\nu(x)\rvert$ and is denoted by
$d_{TV}(\mu,\nu)$. Our main result can now be stated as follows.

######  Theorem 1.

For any real $\theta\in(0,1)$, there is $k_{0}\geq 3$ with
$k_{0}=O(\log(1/\theta))$ such that, for any integers $k\geq k_{0}$ and
$\xi\geq 1$, and for any positive real $\alpha\leq 2^{0.039k}$, the following
holds.

There is an efficient algorithm to sample from the satisfying assignments of a
random $k$-CNF formula $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$ within
$n^{-\xi}$ total variation distance of the uniform distribution. The algorithm
runs in time $O(n^{1+\theta})$, and succeeds w.h.p. over the choice of $\Phi$.

Using standard techniques from the literature, this $O(n^{1+\theta})$ uniform
sampling algorithm can be used to obtain a randomised approximation scheme for
counting satisfying assignments of $\Phi$ in time
$O(n^{2+\theta}/\varepsilon^{2})$, where $\varepsilon$ is the multiplicative
error, see [18, Section 7] and Remark 49 for details.

We note here that, independently of this work, Chen, Mani, and Moitra [9] and
He, Wu, and Wang [23] obtained sampling algorithms. The approach of [9] is
also based on spectral independence but uses a different analysis technique
that works up to roughly $2^{k/52}$, whereas the approach of [23] is based on
bounding chains and works up to densities roughly equal to $2^{k/3}$.

##  2 Proof outline

Our nearly linear-time sampling algorithm is based on running a Markov chain;
this is a standard technique in approximate counting, where typically one runs
a Markov chain on the whole state space that converges to the desired
distribution. The twist in $k$-SAT is that the state space of the Markov chain
needs to be carefully selected in order to avoid certain bottleneck phenomena
that impede fast convergence. This approach has been recently applied to
bounded-degree $k$-CNF formulas [18, 27, 19, 26] building on the work of
Moitra [32] and using the Markov chain known as single-site Glauber dynamics.
The main difficulties in all of these works is that the usual distribution
properties that are typically used to obtain fast algorithms (such as
correlation decay and spatial mixing) fail on the set of all SAT solutions,
and in fact even ensuring a connected state space is a major problem. Working
around this is one of the main challenges for us too, and in the random
$k$-SAT setting it is further aggravated by the fact that a linear number of
variables have degrees much higher than average. In fact, w.h.p., a good
portion of vertices have degrees depending on $n$. with the maximum degree of
the formula scaling as $\log n/\log\log n$.

This poses several new challenges for the Markov chain approach to work in our
setting. First of all, we have to ensure that the set of satisfying
assignments that our Markov chain considers has good connectivity properties.
We address this problem in Section 2.1 of this proof outline, where we find a
suitable subset of variables where we can run the Glauber dynamics; this part
is inspired by Moitra’s “marking” approach, though here we need to add an
extra layer of marking to facilitate later the analysis of the Markov chain.
Second and more importantly, state-of-the-art arguments for bounding the
mixing time of the single-site Glauber dynamics on $k$-CNF formulas, such as
[27, 18] break under the presence of high-degree variables. We focus on this
in Section 2.2, where we outline a novel argument that analyses the mixing
time of the uniform-block Glauber dynamics using recent advances in spectral
independence [3, 29, 4, 7]. This is the first application of the spectral-
independence framework for $k$-CNF formulas, where the absence of correlation
decay limits the application of standard techniques (based on self-avoiding
walk trees [4, 7]). To obtain our spectral-independence bounds we need to
combine the probabilistic structure of satisfying assignments with the local
sparsity properties of the random formula. The third challenge in our approach
is simulating the individual steps of the uniform-block Glauber dynamics since
they involve updating a linear number of variables, making the computation of
the transition probabilities more challenging. To this end, we need to
initialise our block Glauber dynamics to random values (instead of an
arbitrary assignment that is typically used as initialisation), and show that
the formula breaks into small tree-like connected components that allows us to
do the relevant computations throughout the algorithm’s execution (cf. Section
2.3). Based on these pieces, the full algorithm is presented in Section 2.4.

###  2.1 Marking variables in the random $k$-SAT model

In order to ensure good connectivity properties which are essential for fast
convergence of the relevant Markov chain, our algorithm runs Glauber dynamics
on a large subset $\mathcal{V}_{\mathrm{m}}$ of so-called “marked” variables
of the random formula, leaving the rest of the variables unassigned. The
variables in $\mathcal{V}_{\mathrm{m}}$ are chosen in a way that ensures that
their marginals are near $1/2$, which is important for ensuring rapid mixing.
Moitra [32] introduced a random “marking” procedure to identify such a subset
of variables in the bounded-degree case. The presence of high-degree variables
impedes a direct application of this technique in the random-formula setting,
but in [21] the authors show that by temporarily removing a small linear
number of “bad” clauses that contain high-degree variables one can also
achieve marginals near $1/2$ for an appropriate set of variables in the random
$k$-SAT model. Here we further refine these arguments as we need more control
over the high-degree variables of the formula in order to conclude rapid
mixing of the Glauber dynamics. Recall that the degree of a variable $v$ is
the number of occurrences of literals involving the variable $v$ in $\Phi$ and
that the maximum degree of the formula $\Phi$ is the maximum degree among its
variables. The following important definitions will be used throughout the
paper. We usually use $\mathcal{V}$ to denote the set of variables and
$\mathcal{C}$ to denote the set of clauses of a $k$-CNF formula $\Phi$. For
any $c\in\mathcal{C}$ we denote by $\operatorname{var}(c)$ the set of
variables appearing in $c$, and for any $S\subseteq\mathcal{C}$ we denote
$\operatorname{var}(S)=\bigcup_{c\in S}\operatorname{var}(c)$.

######  Definition 2 ($r$, $r_{0}$, $\delta$, high-degree, $\Delta$,
$\alpha_{0}$).

Let $r:=0.1178$, $r_{0}:=0.117841$, and $\delta=0.00001$. Let $k\geq 3$ be an
integer. Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula. We say
that a variable $v\in\mathcal{V}$ is _high-degree_ if the degree of $v$ is at
least $\Delta:=\lceil 2^{(r_{0}-2\delta)k}\rceil$. Most of our technical
results consider random $k$-CNF formulas with density at most
$\alpha_{0}:=2^{(r_{0}-2\delta)k}/k^{3}$.

The bottleneck for the density threshold of Theorem 1 comes from our mixing
time results, see Section 2.2. Some of the time we also consider densities
$\alpha\leq 2^{rk}$. The constant $r$ satisfies $r<r_{0}$, where $r_{0}$ will
be relevant when establishing a marking of the variables. We could have chosen
any value of $r$ that is less than $r_{0}$.

We refer to Section 4 for details on our procedure to determine the bad
variables/clauses of the formula $\Phi$. Roughly, bad variables consist of
high-degree variables (as in Definition 2), plus those variables that appear
in a clause with at least two other bad variables (recursively); bad clauses
are those clauses that contain at least three bad variables. We use
$\mathcal{V}_{\mathrm{bad}}$ and $\mathcal{C}_{\mathrm{bad}}$ to denote the
sets of bad variables and clauses. We use
$\mathcal{V}_{\mathrm{good}}=\mathcal{V}\setminus\mathcal{V}_{\mathrm{bad}}$
to denote the set of _good variables_ , and
$\mathcal{C}_{\mathrm{good}}=\mathcal{C}\setminus\mathcal{C}_{\mathrm{bad}}$
to denote the set of _good clauses_. The following proposition, proved in
Section 4, summarises the main properties of the above sets.

######  Proposition 3.

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula. For any
$c\in\mathcal{C}_{\mathrm{good}}$, we have
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{bad}}\rvert\leq 2$, and
for any $c\in\mathcal{C}_{\mathrm{bad}}$, we have
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{good}}\rvert=0$.
Moreover, every good variable has degree less than $\Delta$. There is a
procedure to determine $\mathcal{C}_{\mathrm{bad}}$ that runs in time
$O(n+mk)$, where $n$ is the number of variables of $\Phi$ and $m$ is the
number of clauses of $\Phi$.

It turns out that, w.h.p. over the choice of $\Phi$, most clauses (and
variables) in the random formula $\Phi$ are good, see Lemma 15 for a precise
statement. At this stage, it would be natural to try to rework the Markov
chain approach of [18]. To do this, we would split the set of good variables
in _marked variables_ and _control variables_ in such a way that marked
variables have marginals close to $1/2$. Then we run the Glauber dynamics on
the set of marked variables. However, as we explain in Section 2.2, the state-
of-the-art techniques used to analyse the mixing time of the single-site
Glauber dynamics on bounded-degree formulas do not generalise to the random
$k$-SAT setting; the main reason for this is that they fail to capture the
effect that the high-degree variables have on the marginal probabilities of
other variables. Therefore, we need to develop an alternative approach that is
robust against the presence of high-degree variables. Our main contribution is
an argument to apply the spectral independence framework [7, 8] to the random
$k$-SAT model that leads to nearly linear sampling algorithms. To do this, it
is important to introduce a third type of good variables, which we call the
_auxiliary variables_. This motivates the following definition of marking.

######  Definition 4 ($r$-distributed, $r$-marking).

Let $r>0$. Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula and $V$
be a subset of $\mathcal{V}_{\mathrm{good}}$. We say that $V$ is _$r$
-distributed_ if for each $c\in\mathcal{C}_{\mathrm{good}}$ we have
$\lvert\operatorname{var}(c)\cap V\rvert\geq r(k-3)$.

An _$r$ -marking_ of $\Phi$ is a partition
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
of the variables of $\Phi$ such that

  1. 1.

$\mathcal{V}_{\mathrm{c}}$ contains all the bad variables and the set
$\mathcal{V}_{\mathrm{c}}\setminus\mathcal{V}_{\mathrm{bad}}$ is
$(2r)$-distributed;

  2. 2.

the sets of good variables $\mathcal{V}_{\mathrm{m}}$ and
$\mathcal{V}_{\mathrm{a}}$ are $r$-distributed.

The variables in $\mathcal{V}_{\mathrm{m}}$ are called _marked_ variables, the
variables in $\mathcal{V}_{\mathrm{a}}$ are called _auxiliary_ variables, and
the variables in $\mathcal{V}_{\mathrm{c}}$ are called _control_ variables.

In Section 5 we show that random $k$-CNF formulas have $r_{0}$-markings when
the density $\alpha$ is below the threshold
$\alpha_{0}=2^{(r_{0}-2\delta)k}/k^{3}$, and that the marginals of marked and
auxiliary variables are close to $1/2$; this is where the value of $r_{0}$
becomes important in the argument. We collect these results in Proposition 6
below; first we give some relevant definitions.

######  Definition 5 ($\Omega^{*}$, $\mu_{A}$, $\Omega$, $\Phi^{\Lambda}$,
$\mathcal{C}^{\Lambda}$, $\mathcal{V}^{\Lambda}$, $\Omega^{\Lambda}$).

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula. Let $\Omega^{*}$ be
the set of all assignments $\mathcal{V}\to\\{\mathsf{F},\mathsf{T}\\}$. Given
any subset $A\subseteq\Omega^{*}$, let $\mu_{A}$ be the uniform distribution
on $A$. Let $\Omega$ be the set of satisfying assignments of $\Phi$. For any
partial assignment $\Lambda$ we denote by $\Phi^{\Lambda}$ the formula
obtained by simplifying $\Phi$ under $\Lambda$, i.e., removing the clauses
which are already satisfied by $\Lambda$, and removing false literals from the
remaining clauses. We denote by $\mathcal{C}^{\Lambda}$ and
$\mathcal{V}^{\Lambda}$ the sets of clauses and variables of $\Phi^{\Lambda}$.
Moreover, we denote by $\Omega^{\Lambda}$ the set of satisfying assignments of
$\Phi^{\Lambda}$.

######  Proposition 6.

There is an integer $k_{0}$ such that for any $k\geq k_{0}$ and any density
$\alpha$ with $\alpha\leq\alpha_{0}$ the following holds w.h.p. over the
choice of the random $k$-CNF formula $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$.
There exists an $r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
of $\Phi$. Moreover, for any such marking, for any
$v\in\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}$, any
$V\subseteq\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}$ with
$v\not\in V$, and any $\Lambda\colon V\to\\{\mathsf{F},\mathsf{T}\\}$, we have

$\max\left\\{\operatorname{Pr}_{\mu_{\Omega^{\Lambda}}}\left(v\mapsto\mathsf{F}\right),\operatorname{Pr}_{\mu_{\Omega^{\Lambda}}}\left(v\mapsto\mathsf{T}\right)\right\\}\leq\frac{1}{2}\exp\left(\frac{1}{k2^{(r_{0}+\delta)k}}\right).$

###### Proof.

This follows directly by combining Lemmas 20 and 21, which are stated and
proved in Section 5. ∎

The bound given in Proposition 6 on the marginal probabilities of the marked
and auxiliary variables is exploited several times, and we will explain some
of these applications in this proof outline. We remark that the bound on the
marginals of marked and auxiliary variables holds for _any_ pinning of _any_
subset of these variables, which will be relevant in the spectral independence
argument.

######  Definition 7 (${\left.\kern-1.2pt\mu\right|_{V}}$).

Let $\mathcal{V}$ be a finite set and let
$\Omega\subseteq\\{\mathsf{F},\mathsf{T}\\}^{\mathcal{V}}$. Let $\mu$ be a
distribution over $\Omega$. For a set $V\subseteq\mathcal{V}$, we denote by
${\left.\kern-1.2pt\mu\right|_{V}}$ the marginal distribution of $\mu$ on $V$.

Proposition 6 essentially states that the distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}}}$
is very close to the uniform distribution over all assignments
$\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}\to\\{\mathsf{F},\mathsf{T}\\}$.
This concept is formalised in the following definition.

######  Definition 8 ($\varepsilon$-uniform).

Let $V$ be a set of variables and $\mu$ be a probability distribution over the
assignments $V\to\\{\mathsf{F},\mathsf{T}\\}$. Let $\Lambda\colon
S\to\\{\mathsf{F},\mathsf{T}\\}$ be an assignment of some subset of variables
$S\subseteq V$. We denote by $\operatorname{Pr}_{\mu}(\Lambda)$ the
probability under $\mu$ of the event that the variables in $S$ are assigned
values according to $\Lambda$, and by $\operatorname{Pr}_{\mu}(\cdot|\Lambda)$
the corresponding conditional distribution of $\mu$.

For $\varepsilon\in(0,1)$, we say that the distribution $\mu$ is
_$\varepsilon$ -uniform_ if for any variable $v\in V$ and any partial
assignment $\Lambda\colon V\setminus\\{v\\}\to\\{\mathsf{F},\mathsf{T}\\}$, we
have

$\max\left\\{\operatorname{Pr}_{\mu}\left(\left.v\mapsto\mathsf{F}\right|\Lambda\right),\operatorname{Pr}_{\mu}\left(\left.v\mapsto\mathsf{T}\right|\Lambda\right)\right\\}\leq\frac{1}{2}e^{\varepsilon}.$

From Proposition 6, it follows that the distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$ is
$\varepsilon$-uniform for $\varepsilon=(2^{-(r_{0}+\delta)k}/k)$, so for any
$\Lambda\colon\mathcal{V}_{\mathrm{m}}\to\\{\mathsf{F},\mathsf{T}\\}$, the
probability that the assignment of the marked variables is $\Lambda$ is at
least $(1-e^{\varepsilon}/2)^{\lvert\mathcal{V}_{\mathrm{m}}\rvert}$. The
$\varepsilon$-uniform property also (trivially) guarantees that the space of
assignments
$\Lambda\colon\mathcal{V}_{\mathrm{m}}\to\\{\mathsf{F},\mathsf{T}\\}$ with
$\operatorname{Pr}_{\mu_{\Omega}}(\Lambda)>0$ is connected via single-variable
updates, so we can indeed consider the Glauber dynamics over
$\mathcal{V}_{\mathrm{m}}$. This leads to the main challenge of this work:
does this chain mix rapidly?

###  2.2 Mixing time of the Glauber dynamics on the marked variables

Recently, there has been significant progress in showing that the single-
variable Glauber dynamics on appropriately chosen subsets of variables mixes
quickly for $k$-CNF formulas with bounded degree [18, 26]. These approaches
carefully execute a union bound over paths of clauses connecting marked
variables in order to bound the coupling time between two copies of the chain.
However, these union bound arguments break under the presence of high-degree
variables that are present in random $k$-SAT; this is because the number of
paths connecting marked variables is very sensitive to the max degree of the
formula and in particular grows too fast in our setting. We give a more
detailed discussion in Section 8.1.

Instead, we apply the spectral independence framework to show rapid mixing of
a uniform-block Glauber dynamics, which we review briefly below. Applications
of spectral independence usually exploit decay of correlations to show that
the spectral independence condition holds, see [4, 7, 5] for examples. As we
have mentioned in the introduction, correlation decay fails to hold for
densities exponential in $k$ in the random $k$-SAT model [33] and therefore,
we have to develop a different approach to conclude that the spectral-
independence condition holds in our setting. This is our main contribution in
this work; we show that the marginal distribution on the marked variables,
i.e., ${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$, is
$(\varepsilon\log n)$-spectrally independent for some $\varepsilon>0$ that can
be made arbitrarily small for sufficiently large $k$. Our argument builds on
the coupling idea of Moitra [32] (as refined in [21] for random $k$-SAT) and
relates the spectral independence condition to the expected number of failed
clauses in this coupling process. This allows us to exploit the local sparsity
properties of the random $k$-SAT model to analyse the mixing time of the
Glauber dynamics.

A caveat here is that the spectral independence of
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$ is not
enough on its own to conclude fast mixing of the single-site Glauber dynamics.
The most direct way to work around this is to analyse instead the so-called
$\rho$-uniform-block Glauber dynamics that updates $\rho$ vertices at a time
for some $\rho$ that scales linearly in $n$; the main missing ingredient there
is to show that the modified chain can be implemented efficiently which we
discuss in Section 2.3. We next give a quick overview of the relevant
ingredients of the spectral-independence literature that we will need.

####  2.2.1 The $\rho$-uniform-block Glauber dynamics, spectral independence,
and the mixing time

Let $V$ be a finite set of size $M$ and $\mu$ be a distribution over the
assignments $V\to\\{\mathsf{F},\mathsf{T}\\}$. Let $\Omega$ be the set of
assignments $V\to\\{\mathsf{F},\mathsf{T}\\}$ with positive probability under
$\mu$. For an integer $\rho\in\\{1,2,\ldots,\lvert V\rvert\\}$, the
$\rho$-uniform-block Glauber dynamics for $\mu$ is a Markov chain $X_{t}$
where $X_{0}\in\Omega$ is an arbitrary configuration and, for $t\geq 1$,
$X_{t}$ is obtained from $X_{t-1}$ by first picking a subset $S\subseteq V$ of
size $\rho$ uniformly at random, letting $\Lambda_{t}$ be the restriction of
$X_{t}$ to $V\setminus S$, and updating the configuration on $S$ according to
the probability distribution $\mu(\cdot|\Lambda_{t})$. This chain satisfies
the detailed balance equation for $\mu$. Hence, when the chain is irreducible,
for $\varepsilon>0$, we can consider its mixing time
$T_{\mathrm{mix}}(\rho,\varepsilon)=\max_{\sigma\in\Omega}\min\\{t:d_{TV}(X_{t},\mu)\leq\varepsilon\mid
X_{0}=\sigma\\}$. We say that $\mu$ is _$b$ -marginally bounded_ if for all
$v\in V$, $S\subseteq V\setminus\\{v\\}$, $\Lambda\colon
S\to\\{\mathsf{F},\mathsf{T}\\}$ with $\operatorname{Pr}_{\mu}(\Lambda)>0$,
and $\omega\in\\{\mathsf{F},\mathsf{T}\\}$, it either holds that
$\operatorname{Pr}_{\mu}(v\mapsto\omega|\Lambda)=0$ or
$\operatorname{Pr}_{\mu}(v\mapsto\omega|\Lambda)\geq b$. Spectral independence
results have recently been used in the $b$-marginally bounded setting to
obtain fast mixing time of the uniform-block Glauber dynamics [6, 8]. For
$S\subset V$, $\Lambda\colon S\to\\{\mathsf{F},\mathsf{T}\\}$ with
$\operatorname{Pr}_{\mu}(\Lambda)>0$, and $u,v\in V$ with $u\not\in S$ and
$0<\operatorname{Pr}_{\mu}(u\mapsto\mathsf{T}|\Lambda)<1$, the _influence_ of
$u$ on $v$ (under $\mu$ and $\Lambda$) is defined as

$\mathcal{I}^{\Lambda}(u\to
v)=\operatorname{Pr}_{\mu}\left(v\mapsto\mathsf{T}|u\mapsto\mathsf{T},\Lambda\right)-\operatorname{Pr}_{\mu}\left(v\mapsto\mathsf{T}|u\mapsto\mathsf{F},\Lambda\right).$
(1)

The _influence matrix conditioned on $\Lambda$_ is the (two-dimensional)
matrix whose entries consist of ${\mathcal{I}}^{\Lambda}(u\to v)$ over all
relevant $u$ and $v$. We denote by ${\mathcal{I}}^{\Lambda}$ the matrix and by
$\lambda_{1}({\mathcal{I}}^{\Lambda})$ its largest eigenvalue in absolute
value. For a real $\eta>0$, we say that $\mu$ is _$\eta$ -spectrally
independent_ if for all $S\subset V$ and $\Lambda\colon
S\to\\{\mathsf{F},\mathsf{T}\\}$ with $\operatorname{Pr}_{\mu}(\Lambda)>0$ we
have $\lambda_{1}({\mathcal{I}}^{\Lambda})\leq\eta$. From the results of [8],
one can conclude the following bound for the mixing time of the uniform-block
Glauber dynamics, see Appendix B for details.

######  Lemma 9.

The following holds for any reals $b,\eta>0$, any $\kappa\in(0,1)$ and any
integer $M$ with $M\geq\frac{2}{\kappa}(4\eta/b^{2}+1)$. Let $V$ be a set of
size $M$, let $\mu$ be a distribution over the assignments
$V\to\\{\mathsf{F},\mathsf{T}\\}$, let $\Omega=\\{\Lambda\colon
V\to\\{\mathsf{F},\mathsf{T}\\}:\mu(\Lambda)>0\\}$ and let
$\mu_{\min}=\min_{\Lambda\in\Omega}\mu(\Lambda)$. If $\mu$ is $b$-marginally
bounded and $\eta$-spectrally independent, then, for $\rho=\lceil\kappa
M\rceil$ and $C_{\rho}=(2/\kappa)^{4\eta/b^{2}+1}$, we have

$T_{mix}(\rho,\varepsilon)\leq\left\lceil
C_{\rho}\frac{M}{\rho}\left(\log\log\frac{1}{\mu_{\min}}+\log\frac{1}{2\varepsilon^{2}}\right)\right\rceil.$

We are going to consider the uniform-block Glauber dynamics on the marked
variables of $\Phi$, so $V=\mathcal{V}_{\mathrm{m}}$, and the set of states
coincides with the set of assignments
$\mathcal{V}_{\mathrm{m}}\to\\{\mathsf{F},\mathsf{T}\\}$ as all of them have
positive probability. In this setting, the target distribution is
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$. The
distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$ is
$(1/e)$-marginally-bounded as a straightforward consequence of the fact that
it is $(1/k)$-uniform, see Remark 47 for details. Hence, in order to conclude
rapid mixing it remains to establish spectral independence. For this, we are
going to use the well-known fact (see for instance [7]) that, for $S\subset V$
and $\Lambda\colon S\to\\{\mathsf{F},\mathsf{T}\\}$, we have

$\lambda_{1}({\mathcal{I}}_{\Lambda})\leq\max_{u\in V\setminus S}\sum_{v\in
V\setminus S}\lvert\mathcal{I}^{\Lambda}(u\to v)\rvert.$ (2)

####  2.2.2 Spectral independence in the random $k$-SAT model

In this section we state our spectral independence results in the random
$k$-SAT model. The results stated in this section are proved in Section 8. Our
main technical result is the following.

######  Lemma 10.

There is an integer $k_{0}\geq 3$ such that for any integer $k\geq k_{0}$ and
any density $\alpha$ with $\alpha\leq 2^{r_{0}k/3}/k^{3}$ the following holds.
W.h.p. over the choice of the random $k$-CNF formula
$\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$, for any $r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
of $\Phi$, the distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$ is
$(2^{-r_{0}k}\log n)$-spectrally independent.

We are going to describe some of the ideas behind the proof of Lemma 10.
First, we highlight the fact that, due to the presence of high-degree
variables (which form logarithmically-sized connected components), it is hard
to conclude $\eta$-spectral independence with $\eta=O(1)$. This has also been
the case in recent work on $2$-spin systems on random graphs [5], where
instead correlation decay is exploited to prove $\eta$-spectral independence
for some $\eta=o(\log n)$. Here, our $\eta$-spectral independence bound for
$\eta=o_{k}(\log n)$ will be based on an appropriate coupling. Note, in light
of Lemma 9, $\eta=O(\log n)$ is good enough for proving polynomial mixing time
of the uniform-block Glauber dynamics, but we need the improved bound of Lemma
10 in order to conclude the following fast mixing-time result from Lemma 9
(see Section 8). We remark that the more restrictive density threshold
$\alpha\leq 2^{r_{0}k/3}/k^{3}$ in the statement of Lemma 10 arises in the
union bound given in the proof of this lemma, and that for large enough $k$ we
have $2^{0.039k}\leq 2^{r_{0}k/3}/k^{3}$. We can now state our mixing time
result.

######  Lemma 11.

There is a function $k_{0}(\theta)=\Theta(\log(1/\theta))$ such that, for any
$\theta\in(0,1)$, for any integer $k\geq k_{0}(\theta)$ and any density
$\alpha$ with $\alpha\leq 2^{0.039k}$ the following holds. W.h.p. over the
choice of the random $k$-CNF formula $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$,
for any $r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
of $\Phi$ and for $\rho=\lceil
2^{-k-1}\lvert\mathcal{V}_{\mathrm{m}}\rvert\rceil$, the $\rho$-uniform-block
Glauber dynamics for updating the marked variables has mixing time
$T_{mix}(\rho,\varepsilon/2)\leq T:=\lceil
2^{2k+3}n^{\theta}\log\frac{2n}{\varepsilon^{2}}\rceil$.

Lemma 11 is stated for the block size $\rho=\lceil
2^{-k-1}\lvert\mathcal{V}_{\mathrm{m}}\rvert\rceil$, but it could be proved
more generally when $\rho=c\lvert\mathcal{V}_{\mathrm{m}}\rvert$ and
$c\in(0,1)$. The fact that
$\rho\leq\lvert\mathcal{V}_{\mathrm{m}}\rvert/2^{k}$ in the statement will be
relevant in implementing efficiently the dynamics, discussed in Section 2.3.

Our approach to prove $\eta$-spectral independence significantly differs from
those that in two-spin systems, where it is enough to study sum of influences
over trees (thanks to the tree of self-avoiding walks) and exploit decay of
correlations in this setting (very roughly, the further away two vertices are
in the tree, the smaller the influence that one vertex has in the other). Here
we relate influences to the structure of the dependency graph $G_{\Phi}$ by
running a coupling process on the auxiliary variables, and we state this
connection in the upcoming Lemma 38. First we define more formally dependency
graph $G_{\Phi}$.

######  Definition 12 ($G_{\Phi}$).

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula. We define the graph
$G_{\Phi}$ as follows. The vertex set of $G_{\Phi}$ is $\mathcal{C}$ and two
clauses $c_{1}$ and $c_{2}$ are adjacent if and only if
$\operatorname{var}(c_{1})\cap\operatorname{var}(c_{2})\neq\emptyset$. A set
$C\subseteq\mathcal{C}$ is connected if $C$ is connected in the graph
$G_{\Phi}$. We say that two variables $u$ and $v$ are connected in $\Phi$ if
there is a path $c_{1},c_{2},\ldots,c_{\ell}$ in $G_{\Phi}$ with
$u\in\operatorname{var}(c_{1})$ and $v\in\operatorname{var}(c_{\ell})$.

One of the key ideas behind our analysis is exploiting the fact that, in the
random $k$-SAT model, w.h.p. over the choice of the random formula $\Phi$, any
logarithmic-sized set of clauses $Y$ that is connected in $G_{\Phi}$ has
constant tree-excess, that is, the number of edges connecting a pair of
clauses in $Y$ is $\lvert Y\rvert+O(1)$. This saves a factor of $\Delta$ in
the spectral independence bound by ensuring that there is a large independent
set of clauses in $Y$. We also obtain improved analysis by restricting the
coupling process to auxiliary variables. This enables us to get exponentially
small bounds (in $k$) on the influences between marked variables.

###  2.3 Analysis of the connected components of $\Phi^{\Lambda}$

In this section we deal with the third challenge mentioned at the beginning of
Section 2: can we determine the transition probabilities of the Glauber
dynamics so that we can actually simulate this Markov chain? In fact,
simulating the single-site Glauber dynamics on the marked variables was one of
the main challenges even in the bounded-degree case. In that case this was
resolved using a method that is restricted to the bounded-degree setting (and
whose bottleneck is the analysis of a rejection sampling procedure). A
different procedure is required for the random $k$-SAT setting.

One of the key ideas to simulate this chain is starting the chain on an
assignment $X_{0}\colon\mathcal{V}_{\mathrm{m}}\to\\{\mathsf{F},\mathsf{T}\\}$
drawn from the uniform distribution over all assignments of
$\mathcal{V}_{\mathrm{m}}$. Since the distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}}}$ is
$(1/k)$-uniform (Proposition 6), the transition probabilities of the Glauber
dynamics are close to uniform. This allows us to show that the probability
distribution of the assignment $X_{t}$ that is output by the uniform-block
Glauber dynamics after $t$ steps is also $(1/k)$-uniform (Corollary 22), which
will be important in what follows.

In order to run the $\rho$-uniform-block Glauber dynamics we need to be able
to sample from the distribution $\mu_{\Omega^{\Lambda}}$ for any set
$S\subseteq\mathcal{V}_{\mathrm{m}}$ with $\lvert S\rvert=\rho$ and any
assignment $\Lambda\colon\mathcal{V}_{\mathrm{m}}\setminus
S\to\\{\mathsf{F},\mathsf{T}\\}$ that arises. Unless we can restrict
$\Lambda$, sampling from $\mu_{\Omega^{\Lambda}}$ could potentially be as hard
as sampling from $\mu_{\Omega}$. Fortunately for us, the assignment $\Lambda$
is not completely arbitrary; $\Lambda$ is determined by the random choice of
$S$ and the current state of the Glauber dynamics (which follows a
$(1/k)$-uniform distribution as discussed above). We show that we can
efficiently sample from $\mu_{\Omega^{\Lambda}}$ w.h.p. over the choice of
$\Lambda$. An important observation is that we can efficiently sample from
$\mu_{\Omega^{\Lambda}}$ when the connected components of $G_{\phi^{\Lambda}}$
are logarithmic in size, for example, by applying brute force. This raises the
following question: does $G_{\phi^{\Lambda}}$ break into small connected
components w.h.p. over the choice of $\Lambda$? Lemma 13 gives a positive
answer when $0\leq\rho\leq\lvert V\rvert/2^{k}$. Here the reader can see $V$
as the set of marked variables. The proof of Lemma 13 exploits sparsity
properties of logarithmic-sized connected sets of clauses in random formulas
in conjunction with the fact that $\mu$ is $(1/k)$-uniform.

######  Lemma 13.

There is an integer $k_{0}\geq 3$ such that, for any integer $k\geq k_{0}$,
any density $\alpha\leq 2^{rk}$, and any real number $b$ with $a:=2k^{4}<b$,
the following holds w.h.p. over the choice of $\Phi=\Phi(k,n,\lfloor\alpha
n\rfloor)$.

Let $L$ be an integer satisfying $a\log n\leq L\leq b\log n$. Let $V$ be a set
of good variables of $\Phi$ that is $r_{0}$-distributed, let $\mu$ be a
$(1/k)$-uniform distribution over the assignments
$V\to\\{\mathsf{F},\mathsf{T}\\}$, and let $\rho$ be an integer with
$0\leq\rho\leq\lvert V\rvert/2^{k}$. Consider the following experiment. First,
draw $S\subseteq V$ from the uniform distribution $\tau$ over subsets of $V$
with size $\rho$. Then, sample an assignment $\Lambda$ from
${\left.\kern-1.2pt\mu\right|_{V\setminus S}}$. Denote by $\mathcal{F}$ the
event that that there is a connected set of clauses $Y$ of $\Phi$ with $\lvert
Y\rvert\geq L$ such that all clauses in $Y$ are unsatisfied by $\Lambda$. Then
$\operatorname{Pr}_{S\sim\tau}\left(\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{F}\right)\leq 2^{-\delta kL}\right)\geq 1-2^{-\delta kL}$.

###### Proof sketch.

The proof is in Section 6. For the sake of exposition, we first sketch the
proof in the case $\rho=0$, where the conclusion in the statement reads
$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V}}}\left(\mathcal{F}\right)\leq
2^{-\delta kL}$. At the end of this proof sketch we explain how we extend the
proof to any $\rho$ with $0\leq\rho\leq\lvert V\rvert/2^{k}$.

The first step is exploiting local sparsity properties of random $k$-CNF
formulas to find many variables from $V$ in any sufficiently large connected
set of clauses. Our sparsity results hold for connected sets of clauses with
size at least $2k^{4}\log n$, and let us conclude the following result (stated
as Lemma 26 in Section 6): w.h.p. over the choice of $\Phi$, for every
connected set of clauses $Z\subseteq\mathcal{C}$ we have

$\text{if }\ 2k^{4}\log(n)\leq\lvert Z\rvert\leq b\log(n),\ \text{ then }\
\lvert\operatorname{var}(Z)\cap V\rvert\geq(r_{0}-\delta)k\lvert Z\rvert.$ (3)

The proof of Lemma 26 counts the variables from $V$ in $Z$ by using the fact
that $Z$ does not contain many bad clauses and the fact that there are not
many edges joining clauses in $Z$. In fact, for such a set $Z$, we show that
the number of edges is of order $\lvert Z\rvert+O(1)$, that is, $Z$ has
constant tree-excess (Lemma 24). We also need the following result on random
$k$-CNF formulas. For each clause $c\in\mathcal{C}$, let
$\mathcal{Z}(c,L)=\\{Z\subseteq\mathcal{C}:c\in Z,Z\text{ is connected in
}G_{\Phi},\lvert Z\rvert=L\\}$. Then, w.h.p. over the choice of $\Phi$, [21,
Lemma 40] shows that, as long as $L\geq\log n$,

$\text{for any clause }c\in\mathcal{C}\text{ we have
}\left|\mathcal{Z}(c,L)\right|\leq(9k^{2}\alpha)^{L}.$ (4)

Once we have established (3) and (4), the proof exploits the fact that $\mu$
is close to the uniform distribution. First, we introduce some notation. Let
$L$ be an integer with $a\log n\leq L\leq b\log n$. Let $S=\emptyset$ as we
are dealing with the case $\rho=0$. For $c\in\mathcal{C}$ and
$Z\in\mathcal{Z}(c,L)$, we denote by $\mathcal{E}_{1}(Z,S)$ the event that
$Z\subseteq\mathcal{C}^{\Lambda}$, where $\Lambda$ is drawn from
${\left.\kern-1.2pt\mu\right|_{V\setminus S}}$, see Definition 7. We keep
track of $S$ in the notation here as this is relevant in the general case.
Recall that $Z\subseteq\mathcal{C}^{\Lambda}$ means that none of the clauses
in $Z$ are satisfied by the assignment $\Lambda$ (Definition 5). The first
observation is that the event $\mathcal{F}$ from the statement satisfies
$\mathcal{F}=\bigcup_{c\in\mathcal{C},Z\in\mathcal{Z}(c,L)}\mathcal{E}_{1}(Z,S)$.
We then claim that for any $c\in\mathcal{C}$ and $Z\in\mathcal{Z}(c,L)$ we
have

$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)\leq\frac{2^{-\delta
kL}}{\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert},$ (5)

so the result would follow from a union bound over $c$ and $Z$. Let us give
some insight on how we prove (5). Let $c\in\mathcal{C}$ and
$Z\in\mathcal{Z}(c,L)$. The main idea is that, if all clauses in $Z$ are
unsatisfied by $\Lambda$ then, when we sampled
$\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus S}}$, for each variable
$v$ in $\operatorname{var}(Z)\cap(V\setminus S)$ we picked the value that does
not satisfy the clauses of $Z$ containing $v$. Thus, we can bound the
probability that all clauses in $Z$ are unsatisfied as a product, over the
variables in $\operatorname{var}(Z)\cap(V\setminus S)$, of probabilities, each
factor corresponding to the probability that a variable is assigned a certain
value (under some careful conditioning, see the proof in Section 6 for
details). Since the distribution $\mu$ is $(1/k)$-uniform, each one of these
factors can be bounded by $\exp(1/k)/2$, obtaining

$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)\leq\left(\frac{1}{2}\exp\big{(}\frac{1}{k}\big{)}\right)^{\lvert\operatorname{var}(Z)\cap(V\setminus
S)\rvert}.$ (6)

In (3) we gave a lower bound on $\lvert\operatorname{var}(Z)\cap V\rvert$,
which can be applied in conjunction with (4) to conclude, after some
calculations, that the bound given in (5) holds.

The case $\rho>0$ is more technical and one has to be more careful in these
calculations. We show that (5) holds when $S$ does not contain many variables
in $\operatorname{var}(Z)\cap V$. A slightly different argument is needed when
going from (6) to (5); here we have to bound
$\lvert\operatorname{var}(Z)\cap(V\setminus S)\rvert$ instead of
$\lvert\operatorname{var}(Z)\cap V\rvert$. It turns out that, as long as the
bound $\lvert\operatorname{var}(Z)\cap V\cap
S\rvert\leq\lvert\operatorname{var}(Z)\cap V\rvert/k$ holds, the calculations
to go from (6) to (5) also hold in this setting. Finally, we show that the
probability that $\lvert\operatorname{var}(Z)\cap V\cap
S\rvert\leq\lvert\operatorname{var}(Z)\cap V\rvert/k$ occurs when picking $S$
is at least $1-2^{\delta kL}$. The proof of this fact is purely combinatorial,
and requires the hypothesis $\rho\leq\lvert V\rvert/2^{k}$, see Section 6 for
details. ∎

Once we have established Lemma 13, we can use it to implement the
$\rho$-uniform-block Glauber dynamics on the marked variables for
$0<\rho\leq\lvert\mathcal{V}_{\mathrm{m}}\rvert$ and complete our sampling
algorithm, which we explicitly state in Section 2.4.

###  2.4 The sampling algorithm

To complete this proof outline, we explicitly describe Algorithm 1, our
algorithm for sampling satisfying assignments of $k$-CNF formulas. The
algorithm uses a method $\operatorname{Sample}(\Phi^{\Lambda},S)$ to sample an
assignment $\tau\colon S\to\\{\mathsf{F},\mathsf{T}\\}$ from the distribution
${\left.\kern-1.2pt\mu_{\Omega^{\Lambda}}\right|_{S}}$. This method exploits
the fact that logarithmic-sized connected set of clauses have constant tree-
excess, which does not hold in the bounded-degree case. This tree-like
property enables us to efficiently sample satisfying assignments on the
connected components of $\Phi^{\Lambda}$ by a standard dynamic programming
argument, see Section 7. Lemma 14 is our main result on
$\operatorname{Sample}(\Phi^{\Lambda},S)$.

######  Lemma 14.

There is an integer $k_{0}\geq 3$ such that, for any integers $k\geq k_{0}$,
$\xi\geq 1$ and any density $\alpha\leq 2^{rk}$, the following holds w.h.p.
over the choice of $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$. Let $V$ be a
subset of variables and let $\Lambda\colon V\to\\{\mathsf{F},\mathsf{T}\\}$ be
a partial assignment such that all the connected components in
$G_{\Phi^{\Lambda}}$ have size at most $2k^{4}(1+\xi)\log(n)$. Then, there is
an algorithm that, for any $S\subseteq\mathcal{V}\setminus V$, samples an
assignment from ${\left.\kern-1.2pt\mu_{\Omega^{\Lambda}}\right|_{S}}$ in time
$O(\lvert S\rvert\log n)$.

The method $\operatorname{Sample}(\Phi^{\Lambda},S)$ is used in Algorithm 1 to
implement each step of the $\rho$-uniform-block Glauber dynamics on the marked
variables. It is also used to extend the assignment of marked variables
computed by the Glauber dynamics to a satisfying assignment of $\Phi$. As a
design choice, this method returns error when the connected components of
$G_{\Phi^{\Lambda}}$ have size larger than $2k^{4}(1+\xi)\log(n)$. We remark
that the probability that $\operatorname{Sample}(\Phi^{\Lambda},S)$ returns
error is very small when running the Glauber dynamics thanks to Lemma 13. We
can now introduce Algorithm 1, which has two parameters $\theta\in(0,1)$ and
$\xi\geq 1$ as in Theorem 1.

0: A $k$-CNF formula $\Phi=(\mathcal{V},\mathcal{C})$ with $n$ variables

Compute the sets of bad/good variables and bad/good clauses for $\Phi$ as in
Proposition 3.

Let $\varepsilon=n^{-\xi}$. Compute a marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
for $\Phi$ as in Lemma 20 with $p=\varepsilon/4$. This succeeds with
probability at least $1-\varepsilon/4$. If this does not succeed, the
algorithm returns error.

For each $v\in\mathcal{V}_{\mathrm{m}}$, sample
$X_{0}(v)\in\\{\mathsf{F},\mathsf{T}\\}$ uniformly at random.

for $t$ from $1$ to $T:=\lceil
2^{2k+3}n^{\theta}\log\frac{2n}{\varepsilon^{2}}\rceil$ do

Choose uniformly at random a set of marked variables
$S\subseteq\mathcal{V}_{\mathrm{m}}$ with size $\rho:=\lceil
2^{-k-1}\lvert\mathcal{V}_{\mathrm{m}}\rvert\rceil$.

Let $\Lambda_{t}$ be the assignment $X_{t-1}$ restricted to
$\mathcal{V}_{\mathrm{m}}\setminus S$.

$Y\leftarrow\operatorname{Sample}(\Phi^{\Lambda_{t}},S)$.

$X_{t}\leftarrow\Lambda_{t}\cup Y$.

end for

$Y\leftarrow\operatorname{Sample}(\Phi^{X_{T}},\mathcal{V}_{\mathrm{a}}\cup\mathcal{V}_{\mathrm{c}})$.

return $X_{T}\cup Y$.

Algorithm 1 The approximate sampling algorithm for satisfying assignments of
random $k$-CNF formulas.

We remark here that Algorithm 1 only works for large enough $k$, and this
hypothesis will be used several times in our arguments. The quantity $T$
defined in this algorithm corresponds to the mixing time of the
$\rho$-uniform-block Glauber dynamics given in Lemma 11.

##  3 Paper outline

The rest of this work is organised as follows. In Section 4 we introduce the
procedure for determining bad clauses. In Section 5 we prove Proposition 6 on
markings of random formulas. In Section 6 we prove our technical result on the
connected components of $\Phi^{\Lambda}$, Lemma 13. In Section 7 we give the
method $\operatorname{Sample}$ and prove Lemma 14. In Section 8 we prove the
results on spectral independence stated in Section 2.2 of the proof outline.
Finally, in Section 9 we complete the proof of Theorem 1 by combining our
mixing time results (Lemma 11), our algorithm to sample from small connected
components (Lemma 14) and our result on the size of the connected components
of $\Phi^{\Lambda}$ (Lemma 13).

To help keep track of the notation and definitions introduced in this work,
the reader is referred to the tables in Appendix C.

##  4 High-degree and bad variables in random CNF formulas

As we noted in the introduction, one of the keys to sampling satisfying
assignments in the unbounded-degree setting is to “sacrifice” a few variables
per clause (treating them separately in the sampling algorithm) and to
(temporarily) remove a small linear number of clauses that contain these. The
point of this is to ensure that the remaining (“good”) clauses have mostly
low-degree variables (at most two bad ones) and also that the rest of the
clauses (the “bad” ones) form small connected components that interact with
the good clauses in a manageable way.

Recall that high-degree variables were introduced in Definition 2. By standard
arguments about random graphs, one can determine that, w.h.p. over the choice
of $\Phi$, the number of high-degree variables of $\Phi$ is bounded. We want
to identify the clauses of $\Phi$ that have at most $2$ high-degree variables,
since clauses with a lot of high-degree variables will interfere with our
sampling algorithms. This motivates the following construction. The _bad
variables_ and _bad clauses_ of $\Phi$ are identified by running the process
given in Algorithm 2. Here $\mathcal{V}_{\mathrm{bad}}$ denotes the set of bad
variables and $\mathcal{C}_{\mathrm{bad}}$ denotes the set of bad clauses.

0: A $k$-CNF formula $\Phi=(\mathcal{V},\mathcal{C})$

$\mathcal{V}_{0}\leftarrow\text{ the set of high-degree variables}$

$\mathcal{C}_{0}\leftarrow\text{ the set of clauses with at least }3\text{
variables in }\mathcal{V}_{0}$

$i\leftarrow 0$

while $i=0$ or $\mathcal{V}_{i}\neq\mathcal{V}_{i-1}$ do

$i\leftarrow i+1$

$\mathcal{V}_{i}\leftarrow\mathcal{V}_{i-1}\cup\operatorname{var}(\mathcal{C}_{i-1})$

$\mathcal{C}_{i}\leftarrow\\{c\in\mathcal{C}:\lvert\operatorname{var}(c)\cap\mathcal{V}_{i}\rvert\geq
3\\}$

end while

$\mathcal{C}_{\mathrm{bad}}\leftarrow\mathcal{C}_{i}$ and
$\mathcal{V}_{\mathrm{bad}}\leftarrow\mathcal{V}_{i}$

return $\mathcal{V}_{\mathrm{bad}},\mathcal{C}_{\mathrm{bad}}$

Algorithm 2 Computing bad variables and bad clauses

We define the _good clauses_ of $\Phi$ as
$\mathcal{C}_{\mathrm{good}}=\mathcal{C}\setminus\mathcal{C}_{\mathrm{bad}}$
and the _good variables_ of $\Phi$ as
$\mathcal{V}_{\mathrm{good}}=\mathcal{C}\setminus\mathcal{V}_{\mathrm{bad}}$.
We will use the observations given in Proposition 3 several times in this
work.

######  Proposition 3.

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula. For any
$c\in\mathcal{C}_{\mathrm{good}}$, we have
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{bad}}\rvert\leq 2$, and
for any $c\in\mathcal{C}_{\mathrm{bad}}$, we have
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{good}}\rvert=0$.
Moreover, every good variable has degree less than $\Delta$. There is a
procedure to determine $\mathcal{C}_{\mathrm{bad}}$ that runs in time
$O(n+mk)$, where $n$ is the number of variables of $\Phi$ and $m$ is the
number of clauses of $\Phi$.

###### Proof.

In this proof we briefly explain the implementation of Algorithm 2 announced
in the statement. First, for each clause $c$ we keep track of the number of
bad variables in $\operatorname{var}(c)$, denoted $\operatorname{bad}(c)$. We
also have a stack of of bad variables $S_{\mathcal{V}}$ that are yet to be
processed by the algorithm. At the start of the algorithm, we set
$S_{\mathcal{V}}\leftarrow\mathcal{V}_{0}$. While $S_{\mathcal{V}}$ is non-
empty, we take the variable $v$ on the top of the stack and increase
$\operatorname{bad}(c^{\prime})$ by $1$ for those clauses $c^{\prime}$ where
$v$ appears. If any of these updates gives $\operatorname{bad}(c^{\prime})\geq
3$, we add $\operatorname{var}(c^{\prime})$ to the stack $S_{\mathcal{V}}$,
set the variables in $\operatorname{var}(c^{\prime})$ as bad and set the
clause $c^{\prime}$ as bad. At the end of this process, $S_{\mathcal{V}}$ is
empty and we have found all the bad variables and bad clauses of $\Phi$. As
every variable is added to the stack at most once and the list
$\operatorname{bad}(\cdot)$ is updated at most $mk$ times (once per literal in
$\Phi$), the running time is $O(n+mk)$. ∎

In our work we need a variation of a result of [21] that controls the number
of bad clauses in connected subgraphs of $G_{\Phi}$. We state this result in
Lemma 15 and prove it in Appendix A.

######  Lemma 15 (Modified version of [21, Lemma 8.16]).

There is an integer $k_{0}\geq 3$ such that for any integer $k\geq k_{0}$ and
any density $\alpha\leq\alpha_{0}=2^{(r_{0}-2\delta)k}/k^{3}$, the following
holds w.h.p. over the choice of the random $k$-CNF formula
$\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$. For every connected set of clauses
$Y$ in $G_{\Phi}$ such that $\lvert\operatorname{var}(Y)\rvert\geq 2k^{4}\log
n$, we have $\lvert Y\cap\mathcal{C}_{\mathrm{bad}}\rvert\leq\lvert
Y\rvert/k$.

Lemma 15 guarantees that, w.h.p. over the choice of $\Phi$, bad clauses are a
minority among all the clauses of $\Phi$. This will be used to show that bad
clauses do not affect significantly the behaviour of our sampling algorithm.
We point out that the definitions of
$\mathcal{V}_{\mathrm{good}},\mathcal{V}_{\mathrm{bad}},\mathcal{C}_{\mathrm{good}}$
and $\mathcal{C}_{\mathrm{bad}}$ given in [21] use the condition
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{i}\rvert\geq k/10$ instead of
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{i}\rvert\geq 3$. Hence, our
definitions of good clauses and good variables are more restrictive. However,
it turns out that, with minor changes, the proof of Lemma 15 given in [21] can
be extended to our setting. These changes are explained in Appendix A.

##  5 Identifying a set of “marked” variables with good marginals

A property that is useful for sampling satisfying assignments is having a high
proportion of variables in each good clause such that the marginals of these
variables are fairly close to $1/2$. That is, having variables which are
roughly equally likely to be true or false in a random satisfying assignment.
The marginals of high-degree variables do vary. However, even in the random
$k$-SAT model it turns out that there are enough variables with marginals near
$1/2$. Following the basic approach of Moitra [32], we partition the good
variables of a random $k$-CNF formula into types. Here we have three type of
variables (instead of two): marked, auxiliary and control variables. The high-
level goal is to do this in such a way that each clause has a good proportion
of each one of these types of variables. We call this construction a marking,
see Definition 4 of the proof outline for the precise definition. For such
marking, we will show that as long as the control variables are left
unassigned/unpinned, the marginals of the marked and auxiliary variables are
all near $1/2$ as a consequence the Lovász local lemma [17]. We first set up
the notation and results that we need.

It is not difficult to show that in the random $k$-SAT model, w.h.p. over the
choice of the formula $\Phi$, two distinct clauses share at most $2$ variables
(see Lemma 16). Previous work on counting/sampling satisfying assignments had
to analyse subsets of disjoint clauses in order to deal with the fact that
small sets of clauses might share most of their variables. The restriction to
disjoint subsets imposes further restrictions on the maximum degree of the
formula and on the density of the formula in the random $k$-SAT model setting.
Here we manage to exploit Lemma 16 to avoid these restrictions.

######  Lemma 16.

For any $k\geq 3$ and any density $\alpha>0$ (possibly depending on $k$), the
following holds w.h.p. over the choice of the random $k$-CNF formula
$\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$. We have
$\lvert\operatorname{var}(c)\rvert\geq k-1$ and
$\lvert\operatorname{var}(c)\cap\operatorname{var}(c^{\prime})\rvert\leq 2$
for all $c,c^{\prime}\in\mathcal{C}$ with $c\neq c^{\prime}$.

###### Proof.

First, let us prove that, for $k\geq 3$, w.h.p. over the choice of $\Phi$,
$\lvert\operatorname{var}(c)\rvert\geq k-1$ for all $c\in\mathcal{C}$. Let us
denote by $\mathcal{R}_{c}$ the event that a clause $c$ has at least two
repetitions among its variables, that is,
$\lvert\operatorname{var}(c)\rvert\leq k-2$. We claim that
$\operatorname{Pr}(\mathcal{R}_{c})\leq q(k)/n^{2}$, where
$q=\binom{k}{3}+k(k-1)(k-2)(k-3)/4$. To prove this statement we note that the
probability that a variable appears at least $3$ times in $c$ is at most
$\binom{k}{3}n^{k-2}/n^{k}$, and the probability that two distinct variables
are repeated in $c$ is at most $p(k)n(n-1)n^{k-4}/n^{k}$ for
$p(k)=k(k-1)(k-2)(k-3)/4$. Hence, by adding up both cases, we find that
$\operatorname{Pr}(\mathcal{R}_{c})\leq q(k)/n^{2}$, and
$\operatorname{Pr}(\bigcup_{c\in\mathcal{C}}\mathcal{R}_{c})\leq
q(k)m/n^{2}\leq q(k)\alpha/n=O(1/n)$, so the result follows.

Let $c,c^{\prime}\in\mathcal{C}$ with $c\neq c^{\prime}$. We study
$\lvert\operatorname{var}(c)\cap\operatorname{var}(c^{\prime})\rvert$,

$\operatorname{Pr}\left(\left|\operatorname{var}(c)\cap\operatorname{var}(c^{\prime})\right|\geq
3\right)\leq\frac{n(n-1)(n-2)n^{2(k-3)}(k(k-1)(k-2))^{2}}{n^{2k}}\leq\frac{k^{6}}{n^{3}}.$

Therefore, the probability that there is a pair of clauses $c,c^{\prime}$ with
$\lvert\operatorname{var}(c)\cap\operatorname{var}(c^{\prime})\rvert\geq 3$ is
bounded from above by
$\frac{m(m-1)}{2}\frac{k^{6}}{n^{3}}\leq\frac{\alpha^{2}}{2}\frac{k^{6}}{n}=O\left(\frac{1}{n}\right)$,
which finishes the proof. ∎

We will use the asymmetric version of the Lovász local lemma (LLL), proved by
Lovász and originally published in [38]. Before stating this result, let us
introduce some notation. Let $\mathcal{P}$ be a finite collection of mutually
independent random variables. Let $B$ an event that is a function of the
random variables in $\mathcal{P}$. Let $\mathcal{A}$ be a collection of events
that are a function of the random variables in $\mathcal{P}$. We define
$\Gamma(B)$ as the set of events $A\in\mathcal{A}$ such that $A\neq B$ and $A$
and $B$ are not independent. In this setting, $\operatorname{Pr}_{P}(B)$ is
the probability that the event $B$ holds when sampling all the random
variables in $\mathcal{P}$.

######  Theorem 17 (Asymmetric Lovász local lemma, [22, Theorems 1.1 and
2.1]).

Let $\mathcal{P}$ be a finite collection of mutually independent random
variables. Let $\mathcal{A}$ be a collection of events that are a function of
the random variables in $\mathcal{P}$. If there exists a function
$x:\mathcal{A}\to(0,1)$ such that, for all $A\in\mathcal{A}$, we have

$\operatorname{Pr}_{P}\left(A\right)\leq
x(A)\prod_{N\in\Gamma(A)}\left(1-x(N)\right),$

then
$\operatorname{Pr}_{P}\left(\,\bigcap\nolimits_{A\in\mathcal{A}}\overline{A}\,\right)>0$.
Furthermore, for any event $B$ that is a function of the random variables in
$\mathcal{P}$, we have

$\operatorname{Pr}_{P}\left(B\left|\,\bigcap\nolimits_{A\in\mathcal{A}}\overline{A}\right.\right)\leq\operatorname{Pr}_{P}\left(B\right)\prod_{A\in\Gamma(B)}\big{(}1-x(A)\big{)}^{-1}.$

We are going to apply the LLL in Lemma 20 to find an $r_{0}$-marking of $\Phi$
(Definition 4), w.h.p. over the choice of the random formula, for some
appropriate $r_{0}\in(0,1)$. Before proving Lemma 20, let us highlight how
strong the properties of an $r$-marking are. First, the fact that a set of
marked variables is $r$-distributed (Definition 4) will allow us to find,
w.h.p. over the choice of $\Phi$, a good amount of marked variables in any set
of clauses, even if the set includes bad clauses, see Lemma 26 for a precise
statement. This result is an essential ingredient in our proofs. Secondly, as
long as the control variables are left unassigned, the marginals of the marked
and auxiliary variables will be near $1/2$ as a consequence of the LLL, as we
show later in this section (Lemma 21). We remark that, in the definition of
$r$-distributed set of variables, we ask for $\lvert\operatorname{var}(c)\cap
V\rvert\geq r(k-3)$ instead of $\lvert\operatorname{var}(c)\cap V\rvert\geq
rk$ to account for the fact that w.h.p. a good clause has at most a repeated
variable (Lemma 16) and at most two bad variables (Proposition 3), which will
come up in the proofs presented in this section. First, we need the following
definition.

######  Definition 18 ( $\Phi_{\mathrm{good}}$, $\Phi_{\mathrm{bad}}$).

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula. Let
$\Phi_{\mathrm{good}}=(\mathcal{V}_{\mathrm{good}},\mathcal{C}_{\mathrm{good}})$
be the CNF formula obtained by taking the good clauses of $\Phi$ and ignoring
the bad variables appearing in them. Let $\Phi_{\mathrm{bad}}$ be the $k$-CNF
formula with variables $\mathcal{V}_{\mathrm{bad}}$ and clauses
$\mathcal{C}_{\mathrm{bad}}$.

Note that in $G_{\Phi_{\mathrm{good}}}$ two clauses $c_{1}$ and $c_{2}$ in
$\mathcal{C}_{\mathrm{good}}$ are adjacent if and only if
$\operatorname{var}(c_{1})\cap\operatorname{var}(c_{2})\cap\mathcal{V}_{\mathrm{good}}\neq\emptyset$.
By definition of good variables, the maximum degree in
$G_{{\Phi_{\mathrm{good}}}}$ is at most $k(\Delta-1)$, which will be important
when applying the LLL. We also need the following version of Chernoff’s
bounds.

######  Lemma 19 (Chernoff’s bounds - [35, Theorem 2.1 and Corollary 4.1]).

Let $n\in\mathbb{N}$, $p\in[0,1]$, and let $X_{1},\ldots,X_{n}$ be $n$
independent random variables with $X_{j}\in\\{0,1\\}$ and
$\operatorname{Pr}(X_{j}=1)=p\,$ for all $j=1,\ldots,n$. Let
$X=\sum_{j=1}^{n}X_{j}$. Then, for any $r\in(p,1)$ and any $s\in(0,p)$, we
have $\operatorname{Pr}\left(X\geq rn\right)\leq e^{-D(r,p)n}$ and
$\operatorname{Pr}\left(X\leq sn\right)\leq e^{-D(s,p)n}$, where, for reals
$x,y\in(0,1)$,
$D(x,y):=x\log\left(x/y\right)+(1-x)\log\left((1-x)/(1-y)\right)$ is the
Kullback-Leibler divergence.

We can now state the main result of this section. The Lovász local lemma ideas
in the proof of Lemma 20 are standard in the literature since the work of
Moitra [32] but the quantities involved are adapted to our setting.

######  Lemma 20.

There is a positive integer $k_{0}$ such that for any $k\geq k_{0}$ and any
density $\alpha$ with $\alpha\leq\alpha_{0}$ the following holds w.h.p. over
the choice of the random $k$-CNF formula $\Phi=\Phi(k,n,\lfloor\alpha
n\rfloor)$:

  1. 1.

there exists a partial assignment of bad variables that satisfies all bad
clauses;

  2. 2.

there exists an $r_{0}$-marking of $\Phi$. Furthermore, for any $p\in(0,1)$,
such an $r_{0}$-marking can be computed with probability at least $1-p$ in
time $O(n\log(1/p))$.

###### Proof of Lemma 20.

We note that for any $k\geq 4$ our density
$\alpha\leq\alpha_{0}=2^{(r_{0}-2\delta)k}/k^{3}$ is below the threshold
$c_{k}>1.3836\cdot 2^{k}/k$ established in [20, Theorem 1.3]. For densities
below this threshold, w.h.p. over the choice of $\Phi$, there is a satisfying
assignment for $\Phi$. When $\Phi$ is satisfiable, we claim that there is an
assignment of the bad variables that satisfies all bad clauses. Indeed, all
the variables in bad clauses are bad (Proposition 3) and, thus, the
restriction of a satisfying assignment to $\mathcal{V}_{\mathrm{bad}}$ must
satisfy all the bad clauses. In the rest of this proof we show that assertion
2 also holds.

In view of Lemma 16, we may assume that $\lvert\operatorname{var}(c)\rvert\geq
k-1$ for all $c\in\mathcal{C}$. Let us find the $r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$.
If all clauses are bad, then we set $\mathcal{V}_{\mathrm{c}}=\mathcal{V}$,
$\mathcal{V}_{\mathrm{m}}=\emptyset$ and $\mathcal{V}_{\mathrm{a}}=\emptyset$.
This is trivially an $r_{0}$-marking for $\Phi$. In the rest of the proof we
assume that there are good variables. We study the following probability
space. For each good variable $v$, we set $v$ as “marked” with probability
$\beta\in(0,1/2)$, “auxiliary” with probability $\beta$ and “control” with
probability $1-2\beta$. This decision is made independently for each good
variable. Each bad variable is set as “control”. Let $\mathcal{P}$ be the set
$\\{P_{v}:v\in\mathcal{V}_{\mathrm{good}}\\}$, where $P_{v}$ is the random
choice made in this experiment for $v$. Let $\mathcal{V}_{\mathrm{m}}$ be the
set of marked variables, let $\mathcal{V}_{\mathrm{a}}$ be the set of
auxiliary variables, and let $\mathcal{V}_{\mathrm{c}}$ be the set of control
variables obtained by running this experiment. For each clause
$c\in\mathcal{C}_{\mathrm{good}}$, let $A_{c}$ be the event that $c$ has less
than $r_{0}(k-3)$ marked variables or less than $r_{0}(k-3)$ auxiliary
variables or less than $2r_{0}(k-3)$ good control variables. We are going to
apply the LLL on the formula $\Phi_{\mathrm{good}}$ so as to show that
$\operatorname{Pr}(\bigcap\nolimits_{c\in\mathcal{C}_{\mathrm{good}}}\overline{A_{c}})>0$.
For each $c\in\mathcal{C}_{\mathrm{good}}$, in view of Proposition 3 and the
fact that $\lvert\operatorname{var}(c)\rvert\geq k-1$, we have
$\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{good}}\rvert\geq k-3$.
Hence, we can apply the Chernoff bound given in Lemma 19 with
$n=\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{good}}\rvert$,
$p=\beta$ and $s=r_{0}$ to obtain, for any choice
$V\in\\{\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}}\\}$,

$\operatorname{Pr}_{P}\left(\lvert\operatorname{var}(c)\cap
V\rvert<r_{0}(k-3)\right)\leq e^{-D(r_{0},\beta)(k-3)}.$

When $V=\mathcal{V}_{\mathrm{c}}\setminus\mathcal{V}_{\mathrm{bad}}$,
$n=\lvert\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{good}}\rvert$,
$p=1-2\beta$ and $s=2r_{0}$ we obtain

$\operatorname{Pr}_{P}\left(\lvert\operatorname{var}(c)\cap
V\rvert<2r_{0}(k-3)\right)\leq e^{-D(2r_{0},1-2\beta)(k-3)}.$

We have chosen $r_{0}$ to be as large as possible under the restrictions that
$D(r_{0},\beta)\geq r_{0}\log 2$ and $D(2r_{0},1-2\beta)\geq r_{0}\log 2$. The
values $\beta=0.571027$ and $r_{0}=0.117841$ satisfy these restrictions. We
conclude that

$\operatorname{Pr}_{P}\left(A_{c}\right)\leq 2\cdot
e^{-D(r_{0},\beta)(k-3)}+e^{-D(2r_{0},1-2\beta)(k-3)}\leq 3\cdot
2^{-r_{0}(k-3)}.$

Let $\Delta_{0}=2^{r_{0}(k-3)}/(3e^{2}k)$ and let $x(A_{c})=1/(k\Delta_{0})$
for all $c\in\mathcal{C}_{\mathrm{good}}$. We check that $x$ satisfies the
condition of the LLL for $\mathcal{P}$ and
$\mathcal{A}=\\{A_{c}:c\in\mathcal{C}_{\mathrm{good}}\\}$. For $k\geq 98$, we
find that $\Delta_{0}>1$ so $x(A_{c})\in(0,1)$ for all
$c\in\mathcal{C}_{\mathrm{good}}$. We note that
$\Gamma(A_{c})=\\{A_{c^{\prime}}:c^{\prime}\in\mathcal{C}_{\mathrm{good}},c^{\prime}\neq
c,\operatorname{var}(c^{\prime})\cap\operatorname{var}(c)\cap\mathcal{V}_{\mathrm{good}}\neq\emptyset\\}$.
The graph $G_{\Phi_{\mathrm{good}}}$, given in Definition 12, has maximum
degree at most $k(\Delta-1)$, so $\lvert\Gamma(A_{c})\rvert\leq
k(\Delta-1)\leq k\Delta_{0}$, where the latter inequality holds for large
enough $k$ as $\Delta=\lceil 2^{(r_{0}-2\delta)k}\rceil$ (recall that
$\delta=0.00001$). Therefore, we have

$x(A_{c})\prod_{N\in\Gamma(A_{c})}\left(1-x(N)\right)\geq\frac{1}{k\Delta_{0}}\left(1-\frac{1}{k\Delta_{0}}\right)^{k\Delta_{0}}\geq\frac{1}{e^{2}k\Delta_{0}}=3\cdot
2^{-r_{0}(k-3)},$

where we used $(1-1/z)^{z}\geq e^{-2}$ for all $z\geq 2$ in the second
inequality. Thus,

$x(A_{c})\prod_{N\in\Gamma(A_{c})}\left(1-x(N)\right)\geq 3\cdot
2^{-r_{0}(k-3)}\geq\operatorname{Pr}_{P}\left(A_{c}\right).$

We conclude that, by the LLL,
$\operatorname{Pr}_{P}\left(\,\bigcap\nolimits_{c\in\mathcal{C}_{\mathrm{good}}}\overline{A_{c}}\,\right)>0$,
so there exists a partition
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
of the variables of $\Phi$ such that
$\mathcal{V}_{\mathrm{bad}}\subseteq\mathcal{V}_{\mathrm{c}}$ and each good
clause contains at least $r_{0}(k-3)$ marked variables, $r_{0}(k-3)$ auxiliary
variables and $2r_{0}(k-3)$ good control variables. That is,
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
satisfies items 1 and 2 of Definition 4 for $r=r_{0}$. Moreover, with
probability at least $1-\delta$, this partition can be computed in
$4n\alpha\Delta_{0}k\log(1/\delta)$ steps with the algorithm of Moser and
Tardos [34]. ∎

In the remaining of this section we bound the marginals of $\mu_{\Omega}$ (the
uniform distribution over the satisfying assignments of the formula $\Phi$,
Definition 5) on any marked and auxiliary variable. In fact, we prove the
stronger result that the marginal distribution of $\mu_{\Omega}$ on
$\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}$ is very close to the
uniform distribution. Recall also that all the variables in bad clauses of
$\Phi$ are bad (Proposition 3), and thus, we can consider the subformula
$\Phi_{\mathrm{bad}}:=(\mathcal{V}_{\mathrm{bad}},\mathcal{C}_{\mathrm{bad}})$,
which is satisfiable under the hypothesis of Lemma 20.

######  Lemma 21.

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula that has an
$r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$.
Then either the formula $\Phi_{\mathrm{bad}}$ is unsatisfiable or the
distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}}}$
is $(2^{-(r_{0}+\delta)k}/k)$-uniform.

###### Proof.

Let us assume that $\Phi_{\mathrm{bad}}$ is satisfiable and let us prove that
the distribution
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}}}$
(Definition 7) is $(2^{-\delta k}/k)$-uniform. Let $\Lambda_{bad}$ be an
assignment of bad variables that satisfies all bad clauses. Let
$v\in\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}$ and let $\Lambda$
be an assignment of
$\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}\setminus\\{v\\}$ to
$\\{\mathsf{F},\mathsf{T}\\}$. Let $\Lambda\cup\Lambda_{bad}$ be the combined
assignment of $\Lambda$ and $\Lambda_{bad}$. We note that
$\operatorname{Pr}_{\mu_{\Omega^{\tau}}}\left(\cdot\right)=\operatorname{Pr}_{\mu_{\Omega}}\left(\cdot\,|\tau\right)$
for any assignment $\tau$ of some variables. In light of this observation, we
are going to prove that

$\max\left\\{\operatorname{Pr}_{\mu_{\Omega^{\Lambda\cup\Lambda_{bad}}}}\left(v\mapsto\mathsf{F}\right),\operatorname{Pr}_{\mu_{\Omega^{\Lambda\cup\Lambda_{bad}}}}\left(v\mapsto\mathsf{T}\right)\right\\}\leq\frac{1}{2}\exp\left(\frac{1}{k2^{(r_{0}+\delta)k}}\right).$
(7)

The result will then follow by the arbitrary choice of $\Lambda_{bad}$ and the
law of total probability. We apply the LLL to the formula
$\Phi^{\prime}:=\Phi^{\Lambda\cup\Lambda_{bad}}$ as follows. Let
$\mathcal{V}^{\prime}$ and $\mathcal{C}^{\prime}$ be the sets of variables and
clauses of $\Phi^{\prime}$. Note that,
$\mathcal{V}^{\prime}\subseteq\mathcal{V}_{\mathrm{good}}$,
$\mathcal{C}^{\prime}\subseteq\mathcal{C}_{\mathrm{good}}$ and
$G_{\Phi^{\prime}}$ is a subgraph of $G_{\Phi_{\mathrm{good}}}$ as all bad
variables have been assigned a value and all bad clauses have been satisfied.
We set $P_{v}=\sigma(v)$ for all $v\in\mathcal{V}^{\prime}$, where
$\sigma\colon\mathcal{V}^{\prime}\to\\{\mathsf{F},\mathsf{T}\\}$ is chosen
uniformly at random from the set of assignments
$\mathcal{V}^{\prime}\to\\{\mathsf{F},\mathsf{T}\\}$, and
$\mathcal{P}=\\{P_{v}:v\in\mathcal{V}^{\prime}\\}$. We define the set
$\mathcal{A}$ as the set containing for all $c\in\mathcal{C}^{\prime}$ the
event $A_{c}=$ “the clause $c$ is not satisfied by the random assignment
$\sigma$”. By the definition of
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$,
there are at least $2r_{0}(k-3)$ good control variables in $c$. Since good
control variables are not assigned a value by $\Lambda\cup\Lambda_{bad}$ and,
thus, they are in $\mathcal{V}^{\prime}$, we have
$\operatorname{Pr}_{P}(A_{c})\leq 2^{-2r_{0}(k-3)}$. Recall that
$\Delta=\lceil 2^{(r_{0}-2\delta)k}\rceil$ (Definition 2). Let
$\Delta_{0}=2^{2r_{0}(k-3)}/(e^{2}k)$ and let $x(A_{c})=\frac{1}{k\Delta_{0}}$
for all $c\in\mathcal{C}^{\prime}$. Let us show that $x$ satisfies the LLL
condition in this setting. In view of
$\Gamma(A_{c})=\\{A_{c^{\prime}}:c^{\prime}\in\mathcal{C}^{\prime}:c^{\prime}\neq
c,\operatorname{var}(c)\cap\operatorname{var}(c^{\prime})\cap\mathcal{V}^{\prime}\neq\emptyset\\}$,
which can be identified with a subset of the neighbours of $c$ in
$G_{\Phi_{\mathrm{good}}}$, and $\lvert\Gamma(A_{c})\rvert\leq k\Delta\leq
k\Delta_{0}$ for large enough $k$, we find that

$x(A_{c})\prod_{N\in\Gamma(A_{c})}\left(1-x(N)\right)\geq\frac{1}{k\Delta_{0}}\left(1-\frac{1}{k\Delta_{0}}\right)^{\Delta_{0}}\geq\frac{1}{e^{2}k\Delta_{0}}=2^{-r_{0}(k-3)}\geq\operatorname{Pr}_{P}\left(A_{c}\right),$

where we used $(1-1/z)^{z}\geq e^{-2}$ for all $z\geq 2$. Let
$A=\\{v\mapsto\mathsf{T}\\}:=\\{\sigma\colon\mathcal{V}^{\prime}\to\\{\mathsf{F},\mathsf{T}\\}\text{
with }\sigma(v)=\mathsf{T}\\}$. In $\Phi^{\prime}$, we have
$\Gamma(A)=\\{A_{c}:c\in\mathcal{C}^{\prime},v\in\operatorname{var}(c)\\}$, so
$\lvert\Gamma(A)\rvert<\Delta$. By the LLL, we obtain

$\operatorname{Pr}_{P}\left(v\mapsto\mathsf{T}\left|\,\bigcap\nolimits_{c\in\mathcal{C}^{\prime}}\overline{A_{c}}\right.\right)\leq\frac{1}{2}\prod_{N\in\Gamma(A)}\big{(}1-x(N)\big{)}^{-1}\leq\frac{1}{2}\left(1-\frac{1}{k\Delta_{0}}\right)^{-(\Delta-1)}.$

For $x>1$, we have $(1-1/x)^{-1}=1+1/(x-1)\leq\exp(1/(x-1))$. We find that

$\operatorname{Pr}_{P}\left(v\mapsto\mathsf{T}\left|\,\bigcap\nolimits_{c\in\mathcal{C}^{\prime}}\overline{A_{c}}\right.\right)\leq\frac{1}{2}\exp\left(\frac{\Delta-1}{k\Delta_{0}-1}\right)\leq\frac{1}{2}\exp\left(\frac{1}{k2^{(r_{0}+\delta)k}}\right),$

where in the latter inequality we used $(p-j)/(q-j)\leq p/q$ for all
$0<j<p\leq q$ and the fact that $\Delta=\lceil 2^{(r_{0}-2\delta)k}\rceil\leq
2^{-(r_{0}+\delta)k}\cdot
2^{2r_{0}(k-3)}/(3e^{2}k)=2^{-(r_{0}+\delta)k}\Delta_{0}$ for large enough
$k$. We note that
$\operatorname{Pr}_{\mu_{\Omega^{\Lambda\cup\Lambda_{bad}}}}\left(\cdot\right)=\operatorname{Pr}_{P}\left(\cdot\,|\bigcap\nolimits_{c\in\mathcal{C}^{\prime}}\overline{A_{c}}\,\right)$,
which completes the proof of one of the upper bounds of (7). The other upper
bound is proved analogously by applying the LLL with
$A=\\{v\mapsto\mathsf{F}\\}$. ∎

The $(2^{-(r_{0}+\delta)k}/k)$-uniform property proved in Lemma 21 is
remarkably strong: as long as the control variables are left unassigned, the
rest of the variables have marginals close to $1/2$, even if some of the
marked and auxiliary variables are pinned / have already been assigned a
value. This property is used several times in this work and will allow us to
prove that, for any pinning of some marked variables, the influences between
marked variables are bounded. In the following corollary we extend Lemma 21 to
the distributions computed by the Glauber dynamics on the marked variables.

######  Corollary 22.

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula such that
$\Phi_{\mathrm{bad}}$ is satisfiable and $\Phi$ has an $r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$.
Let $\rho$ be an integer with
$1\leq\rho<\lvert\mathcal{V}_{\mathrm{m}}\rvert$. Let $t$ be a non-negative
integer and let $X_{t}$ be the (random) assignment obtained after running the
$\rho$-uniform-block Glauber dynamics on the marked variables for $t$ steps,
starting on an assignment $X_{0}$ that is chosen uniformly at random. Then the
probability distribution of $X_{t}$ is $(2^{-(r_{0}+\delta)k}/k)$-uniform.

###### Proof.

Let $\varepsilon=(2^{-(r_{0}+\delta)k}/k)$. Let $V_{1},V_{2},\ldots,$ be a
possible choice of sets of marked variables to be updated when running the
$\rho$-uniform-block Glauber dynamics. We are going to prove that,
conditioning on this choice of sets of variables, the probability distribution
of $X_{t}$ is $\varepsilon$-uniform. Note that by the law of total probability
and the fact that the choice of $V_{1},V_{2},\ldots$ is arbitrary, this is
enough to conclude the result. We carry out the proof by induction on $t$. Let
$\pi_{t}$ be the probability distribution of $X_{t}$. As $\pi_{0}$ is the
uniform distribution over assignments on $\mathcal{V}_{\mathrm{m}}$, the claim
holds for $t=0$. Let us now assume that $\pi_{t-1}$ is $\varepsilon$-uniform
and let us prove that this is also the case for $\pi_{t}$. To show the desired
uniformity of $\pi_{t}$ (cf. Definition 8), consider arbitrary
$v\in\mathcal{V}_{\mathrm{m}}$ and
$\Lambda\colon\mathcal{V}_{\mathrm{m}}\setminus\\{v\\}\to\\{\mathsf{F},\mathsf{T}\\}$,
we need to bound
$\operatorname{Pr}_{\pi_{t}}\left(\left.v\mapsto\mathsf{F}\right|\Lambda\right)$
and
$\operatorname{Pr}_{\pi_{t}}\left(\left.v\mapsto\mathsf{T}\right|\Lambda\right)$.
We distinguish two cases:

  * •

Case $v\in V_{t}$. By definition of the Glauber dynamics, the values of
$X_{t}$ on $V_{t}$ are obtained by sampling from the distribution
$\mu_{\Omega}$ conditioned on the restriction of $X_{t-1}$ to
$\mathcal{V}_{\mathrm{m}}\setminus V_{t}$. Thus, we have
$\operatorname{Pr}_{\pi_{t}}\left(\left.v\mapsto\mathsf{F}\right|\Lambda\right)=\operatorname{Pr}_{\mu_{\Omega^{\Lambda}}}\left(v\mapsto\mathsf{F}\right)$
since the conditioning involving $\Lambda$ sets all the marked variables other
than $v$. As
${\left.\kern-1.2pt\mu_{\Omega}\right|_{\mathcal{V}_{\mathrm{m}}\cup\mathcal{V}_{\mathrm{a}}}}$
is $\varepsilon$-uniform by Lemma 21, we conclude that
$\operatorname{Pr}_{\pi_{t}}\left(\left.v\mapsto\mathsf{F}\right|\Lambda\right)=\operatorname{Pr}_{\mu_{\Omega^{\Lambda}}}\left(v\mapsto\mathsf{F}\right)\leq\frac{1}{2}\exp(\varepsilon)$.
The same bound holds for $v\mapsto\mathsf{T}$.

  * •

Case $v\not\in V_{t}$. If $v$ is not updated in steps $1$ through $t$, then
$\operatorname{Pr}_{\pi_{t}}\left(\left.v\mapsto\mathsf{F}\right|\Lambda\right)=\operatorname{Pr}_{\pi_{0}}\left(v\mapsto\mathsf{F}\right)=1/2$.
Otherwise, let $j$ be the largest integer with $j<t$ such that $v\in V_{j}$.
Let $\Lambda_{j}$ be the restriction of $\Lambda$ to
$\mathcal{V}_{\mathrm{m}}\setminus\bigcup_{i\in\\{j+1,j+2,\ldots,t\\}}V_{i}$.
By the induction hypothesis,
$\operatorname{Pr}_{\pi_{t}}\left(\left.v\mapsto\mathsf{F}\right|\Lambda\right)=\operatorname{Pr}_{\pi_{j}}\left(\left.v\mapsto\mathsf{F}\right|\Lambda_{j}\right)\leq(1/2)\exp(\varepsilon)$.
The same bound holds for $v\mapsto\mathsf{T}$.

As both cases are exhaustive, the proof is concluded. ∎

Previous work on counting/sampling satisfying assignments of $k$-CNF formulas
does not require the use of auxiliary variables, so the marking used is of the
form $(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{c}})$. Here auxiliary
variables play an essential role in bounding the influences between marked
variables as we illustrated in Section 2. In order for this approach to be
successful, we have to show that a large proportion of the variables are
marked. We conclude this section with the following bound on the size of
$\mathcal{V}_{\mathrm{m}}$.

######  Corollary 23.

There is an integer $k_{0}$ such that for any $k\geq k_{0}$ and any density
$\alpha$ with $\alpha\leq\alpha_{0}$ the following holds w.h.p. over the
choice of the random $k$-CNF formula $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$.
For any set of good variables $V$ that is $r_{0}$-distributed we have $\lvert
V\rvert\geq(r_{0}-\delta)(k\alpha/\Delta)n$.

###### Proof.

W.h.p. over the choice of $\Phi$, Lemma 15 holds. We combine this with the
inequality $\alpha_{0}\leq\Delta/k^{3}$ and the fact that a good variable
occurs in at most $\Delta$ good clauses to find that

$\lvert
V\rvert\geq\frac{r_{0}(k-3)\lvert\mathcal{C}_{\mathrm{good}}\rvert}{\Delta}\geq\frac{r_{0}(k-3)}{\Delta}\left(1-\frac{1}{k}\right)\lvert\mathcal{C}\rvert\geq\frac{r_{0}(k-4)}{\Delta}(\alpha
n-1),$

which is at least $(r_{0}-\delta)(k\alpha/\Delta)n$ for large enough $k$. ∎

##  6 Analysis of the connected components of $\Phi^{\Lambda}$

In this section we prove Lemma 13, which bounds the size of the connected
components of $\Phi^{\Lambda}$, where $\Lambda$ is drawn from a
$(1/k)$-uniform distribution over a $r_{0}$-distributed set of good variables.
In order to carry out this proof, we have to understand the structure of
logarithmic-sized sets of clauses of the random $k$-CNF formula $\Phi$.
Section 6.1 is devoted to this purpose. In Section 6.2 we apply the results of
Section 6.1 to obtain a lower bound of the number of marked/auxiliary
variables in logarithmic-sized sets of clauses. Finally, in Section 6.3 we
complete the proof of Lemma 13.

###  6.1 Logarithmic-sized sets of clauses in the random $k$-SAT model

A connected graph $H=(V,E)$ has _tree-excess_ $c\in\mathbb{Z}_{\geq 0}$ if
$\lvert E\rvert=c+\lvert V\rvert-1$. It turns out that, w.h.p. over the choice
of $\Phi$, small connected sets of clauses of $\Phi$ have tree-excess that
only depends on $k$ and the density $\alpha$. This property is established in
Lemma 24 and is essential to our proofs.

######  Lemma 24.

Let $k\geq 3$ be an integer. Let $b>0$ and $\alpha>0$ be real numbers. W.h.p.
over the choice of the random $k$-CNF formula $\Phi=\Phi(k,n,\lfloor\alpha
n\rfloor)$, every connected subset of clauses with size at most $b\log(n)$ has
tree-excess at most $c:=\max\\{1,2b\log(ek^{2}\alpha)\\}$.

###### Proof.

Let $n$ be the number of variables and $m$ be the number of clauses of $\Phi$,
so $m/n\leq\alpha$. Note that the probability that two clauses of $\Phi$ are
not disjoint is at most $k^{2}/n$. Let $\ell\in\\{1,2,\ldots,\lfloor
b\log(n)\rfloor\\}$. We upper bound the probability that there is a connected
subset of clauses of size $\ell$ with tree-excess at least $c+1$ by

$\binom{m}{\ell}\ell^{\ell-2}\binom{\ell(\ell-1)/2}{c+1}\left(\frac{k^{2}}{n}\right)^{\ell+c},$
(8)

where the factors appearing are the following ones:

  * •

$\binom{m}{\ell}$ is the number of subsets of clauses of size $\ell$;

  * •

$\ell^{\ell-2}$ is the number of trees on $\ell$ labelled vertices;

  * •

$\binom{\ell(\ell-1)/2}{c+1}$ is the number of ways to pick $c+1$ pairs of
distinct clauses of a set of size $\ell$;

  * •

$\left(k^{2}/n\right)^{\ell+c}$ is an upper bound of the probability that all
the edges chosen in the two previous items appear in the graph $G_{\Phi}$.

We are going to show that the probability given in (8) is $O(n^{-c/4})$, where
the hidden constant only depends on $k$. If this holds, by a union bound over
$\ell\in\\{1,2,\ldots,\lfloor b\log(n)\rfloor\\}$, we would find that the
probability that there is a connected subset of clauses of $\Phi$ with size at
most $b\log(n)$ and tree-excess at least $c+1$ is $O(b\log(n)n^{-c/4})=o(1)$.
This would complete the proof. Using the inequality
$\binom{p}{q}\leq(ep/q)^{q}$ and $m/n\leq\alpha$ we can bound (8) by

$\displaystyle\left(\frac{em}{\ell}\right)^{\ell}\ell^{\ell-2}\left(\frac{e\ell(\ell-1)/2}{c+1}\right)^{c+1}\left(\frac{k^{2}}{n}\right)^{\ell+c}$
$\displaystyle\leq\left(\frac{em}{\ell}\right)^{\ell}\ell^{\ell-2}\left(\frac{e\ell^{2}/2}{c+1}\right)^{c+1}\left(\frac{k^{2}}{n}\right)^{\ell+c}$
(9)
$\displaystyle=\left(\frac{e}{2c+2}\right)^{c+1}\left(\frac{emk^{2}}{n}\right)^{\ell}\left(\frac{k^{2}\ell^{2}}{n}\right)^{c}$
$\displaystyle\leq\left(\frac{e}{2c+2}\right)^{c+1}\left(ek^{2}\alpha\right)^{\ell}\left(\frac{k^{2}\ell^{2}}{n}\right)^{c}.$

Now we distinguish two cases:

  * •

Case when $ek^{2}\alpha\leq 1$ . We have $c=1$ by definition. Thus, (9) can be
further bounded by

$\left(\frac{e}{2c+2}\right)^{c+1}\left(\frac{k^{2}\ell^{2}}{n}\right)^{c}=O\left(\frac{(\log
n)^{2}}{n}\right)=O\left(n^{-c/4}\right)$

as we wanted.

  * •

Case when $ek^{2}\alpha>1$. Then, as $\ell\leq b\log n$ and
$b\log(ek^{2}\alpha)\leq c/2$ by definition, we have

$\left(ek^{2}\alpha\right)^{\ell}\leq\left(ek^{2}\alpha\right)^{b\log
n}=n^{b\log(ek^{2}\alpha)}\leq n^{c/2}.$

We conclude that (9) can be further bounded by

$\left(\frac{e}{2c+2}\right)^{c+1}\left(\frac{k^{2}\ell^{2}}{\sqrt{n}}\right)^{c}=\left(\frac{e}{2c+2}\right)^{c+1}\left(\frac{k^{4}\ell^{4}}{n}\right)^{c/2}=O\left(n^{-c/4}\right)$

as we wanted, where we used $c>0$. ∎

Recall that in Lemma 15 we established that, in sets of clauses that have at
least $2k^{4}\log n$ variables, the number of bad clauses of $\Phi$ is not too
large. We aim to apply Lemma 15 to logarithmic-sized sets of clauses. In
general, $\lvert Y\rvert$ might be significantly larger than
$\lvert\operatorname{var}(Y)\rvert$, so it is not clear how to apply Lemma 15.
However, in the random $k$-CNF formula setting the following holds.

######  Lemma 25.

Let $k\geq 3$ be an integer and let $a>0$ and $\alpha>0$ be real numbers.
W.h.p. over the choice of $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$, for every
set of clauses $Y$ with $\lvert Y\rvert\geq a\log n$, we have
$\lvert\operatorname{var}(Y)\rvert\geq a\log n$.

###### Proof.

Let $\ell:=\lceil a\log n\rceil-1$ and let $m=\lfloor\alpha n\rfloor$. We
prove the equivalent statement that, w.h.p. over the choice of $\Phi$, for
every set of clauses $Y$ with $\lvert\operatorname{var}(Y)\rvert\leq\ell$, we
have $\lvert Y\rvert\leq\ell$. We note that if there is a set of clauses $Y$
with $\lvert\operatorname{var}(Y)\rvert\leq\ell$ and $\lvert Y\rvert>\ell$,
then for any subset $Y^{\prime}$ of $Y$ with $\lvert Y^{\prime}\rvert=\ell+1$
we have
$\lvert\operatorname{var}(Y^{\prime})\rvert\leq\lvert\operatorname{var}(Y)\rvert\leq\ell$.
Hence, it suffices to prove that there is no set $Y$ of clauses with
$|\operatorname{var}(Y)|\leq\ell$ and $|Y|=\ell+1$. We can assume $n$ is large
enough so that $\ell\leq e\cdot n$.

Let $\mathcal{E}$ be the event that there is a set of clauses $Y$ of size
$\ell+1$ and a set of variables $X$ of size $\ell$ such that all clauses in
$Y$ have all variables in $X$. Then by a union bound

$\displaystyle\operatorname{Pr}\left(\mathcal{E}\right)\leq\binom{m}{\ell+1}\binom{n}{\ell}\left(\frac{\ell}{n}\right)^{(\ell+1)k},$

where the first factor is the number of sets $Y$, the second factor is the
number of sets $X$ and the third factor is the probability that all variables
in the clauses of $Y$ are in $X$. From the well-known bound
$\binom{p}{q}\leq(ep/q)^{q}$, we obtain

$\displaystyle\operatorname{Pr}\left(\mathcal{E}\right)$
$\displaystyle\leq\left(\frac{em}{\ell+1}\right)^{\ell+1}\left(\frac{en}{\ell}\right)^{\ell}\left(\frac{\ell}{n}\right)^{(\ell+1)k}\leq\left(\frac{em}{\ell}\right)^{\ell+1}\left(\frac{en}{\ell}\right)^{\ell+1}\left(\frac{\ell}{n}\right)^{(\ell+1)k}$
$\displaystyle\leq\left(\frac{e\alpha
n}{\ell}\right)^{\ell+1}\left(\frac{en}{\ell}\right)^{\ell+1}\left(\frac{\ell}{n}\right)^{(\ell+1)k}=\left(e^{2}\alpha\frac{\ell^{k-2}}{n^{k-2}}\right)^{\ell+1},$

which is $O(\log(n)/n)$ because $k\geq 3$ and $\ell=O(\log n)$. ∎

###  6.2 Number of marked variables in logarithmic-sized sets of clauses

Our results on random $k$-CNF formulas can now be combined to give a lower
bound on the number of marked / auxiliary variables in logarithmic-sized sets
of clauses. We prove this result in a more general setting by considering a
set of good variables $V$ that is $r_{0}$-distributed for the formula $\Phi$.
The reader can think of $V$ as the set of marked variables or the set of
auxiliary variables. Recall that $\alpha_{0}=2^{(r_{0}-2\delta)k}/k^{3}$
(Definition 2).

######  Lemma 26.

Let $\hat{\delta}\in(0,r_{0})$. There is a positive integer $k_{0}$ such that,
for any integer $k\geq k_{0}$, any density $\alpha\leq\alpha_{0}$ and any real
number $b$ with $2k^{4}<b$, the following holds w.h.p. over the choice of
$\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$. Let $V$ be a set of good variables
that is $r_{0}$-distributed. Then, for every set of clauses $Y$ that is
connected in $G_{\Phi}$ such that $2k^{4}\log(n)\leq\lvert Y\rvert\leq
b\log(n)$, we have $\lvert\operatorname{var}(Y)\cap
V\rvert\geq(r_{0}-\hat{\delta})k\lvert Y\rvert$.

###### Proof.

Let $a=2k^{4}$. We apply Lemma 15 to find that there is $k_{1}$ such that for
$k\geq k_{1}$, w.h.p. over the choice of $\Phi$, for every set of clauses $Y$
that is connected in $G_{\Phi}$,

$\text{if }\ \lvert\operatorname{var}(Y)\rvert\geq a\log(n),\text{ then
}\lvert Y\cap\mathcal{C}_{\mathrm{bad}}\rvert\leq\lvert Y\rvert/k.$ (10)

We apply Lemma 25 with $a=2k^{4}$ to find that, w.h.p. over the choice of
$\Phi$, for every set of clauses $Y$, we have

if $\displaystyle\ \lvert Y\rvert\geq a\log(n),\text{then
}\lvert\operatorname{var}(Y)\rvert\geq a\log(n).$ (11)

Finally, for any $b>0$, we apply Lemma 24, obtaining that, w.h.p. over the
choice of $\Phi$, for every set of clauses $Y$ that is connected in
$G_{\Phi}$,

$\text{if }\lvert Y|\leq b\log n,\text{ then }Y\text{ has tree-excess at most
}c=\max\\{1,2b\log(ek^{2}\alpha)\\}=O(1).$ (12)

Let $Y$ be a set of clauses that is connected in $G_{\Phi}$ such that
$a\log(n)\leq\lvert Y\rvert\leq b\log(n)$. Then, by (11) and (10), we have
$\lvert Y\cap\mathcal{C}_{\mathrm{good}}\rvert\geq\lvert Y\rvert(1-1/k)$. By
definition of $r_{0}$-distributed (Definition 4), each good clause has at
least $r_{0}(k-3)$ variables in $V$. As there are at most $\lvert Y\rvert-1+c$
edges in $G_{\Phi}$ joining clauses in $Y$, see (12), and two distinct clauses
only share at most two variables by Lemma 16, we have

$\displaystyle\lvert\operatorname{var}(Y)\cap V\rvert$ $\displaystyle\geq
r_{0}(k-3)\left(1-\frac{1}{k}\right)\lvert Y\rvert-2(\lvert Y\rvert+c-1)$
$\displaystyle\geq(r_{0}(k-4)-2)\lvert Y\rvert-2(c-1).$

There is $k_{0}\geq k_{1}$ such that for $k\geq k_{0}$, we find that, for any
set of clauses $Y$ that is connected in $G_{\Phi}$ and has $a\log(n)\leq\lvert
Y\rvert\leq b\log(n)$, $\lvert\operatorname{var}(Y)\cap
V\rvert\geq(r_{0}-\hat{\delta}/2)k\lvert Y\rvert-2(c-1)$. Therefore, using
$2(c-1)=O(1)$, for large enough $n$ we conclude that
$\lvert\operatorname{var}(Y)\cap V\rvert\geq(r_{0}-\hat{\delta})k\lvert
Y\rvert$ and the result follows. ∎

###  6.3 Proof of Lemma 13

We use the following result of [21] on the number of connected sets of clauses
in $G_{\Phi}$.

######  Lemma 27 ([21, Lemma 8.6]).

W.h.p. over the choice of $\Phi$, for any clause $c$, the number of connected
sets of clauses in $G_{\Phi}$ with size $\ell\geq\log n$ containing $c$ is at
most $(9k^{2}\alpha)^{\ell}$.

We can now complete the proof of Lemma 13.

######  Lemma 13.

There is an integer $k_{0}\geq 3$ such that, for any integer $k\geq k_{0}$,
any density $\alpha\leq 2^{rk}$, and any real number $b$ with $a:=2k^{4}<b$,
the following holds w.h.p. over the choice of $\Phi=\Phi(k,n,\lfloor\alpha
n\rfloor)$.

Let $L$ be an integer satisfying $a\log n\leq L\leq b\log n$. Let $V$ be a set
of good variables of $\Phi$ that is $r_{0}$-distributed, let $\mu$ be a
$(1/k)$-uniform distribution over the assignments
$V\to\\{\mathsf{F},\mathsf{T}\\}$, and let $\rho$ be an integer with
$0\leq\rho\leq\lvert V\rvert/2^{k}$. Consider the following experiment. First,
draw $S\subseteq V$ from the uniform distribution $\tau$ over subsets of $V$
with size $\rho$. Then, sample an assignment $\Lambda$ from
${\left.\kern-1.2pt\mu\right|_{V\setminus S}}$. Denote by $\mathcal{F}$ the
event that that there is a connected set of clauses $Y$ of $\Phi$ with $\lvert
Y\rvert\geq L$ such that all clauses in $Y$ are unsatisfied by $\Lambda$. Then
$\operatorname{Pr}_{S\sim\tau}\left(\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{F}\right)\leq 2^{-\delta kL}\right)\geq 1-2^{-\delta kL}$.

###### Proof.

Since $\delta=0.00001$, $a=2k^{4}$, $r=0.1178$, and $r_{0}=0.117841$, we can
pick $k_{0}$ large enough so that for all $k\geq k_{0}$ we have

$2^{rk}\leq\frac{2^{(r_{0}-3\delta)k}}{18ek^{3}}\leq\alpha_{0}=2^{(r_{0}-2\delta)k}/k^{3}.$
(13)

We apply Lemma 26 with our choices of $b$ and with $\hat{\delta}=\delta$ to
conclude that, w.h.p. over the choice of $\Phi$, for every connected set of
clauses $Z\subseteq\mathcal{C}$ we have

$\text{if }\ a\log(n)\leq\lvert Z\rvert\leq b\log(n),\ \text{ then }\
\lvert\operatorname{var}(Z)\cap V\rvert\geq(r_{0}-\delta)k\lvert Z\rvert.$
(14)

We also need the following result on random $k$-CNF formulas. For each clause
$c\in\mathcal{C}$, let

$\mathcal{Z}(c,L)=\\{Z\subseteq\mathcal{C}:c\in Z,Z\text{ is connected in
}G_{\Phi},\lvert Z\rvert=L\\}.$

Then, w.h.p. over the choice of $\Phi$, Lemma 27 shows that, as long as
$L\geq\log n$,

$\text{for any clause }c\in\mathcal{C}\text{ we have
}\left|\mathcal{Z}(c,L)\right|\leq(9k^{2}\alpha)^{L}.$ (15)

The facts that we have just established using Lemma 26 and Lemma 27 are all
the properties of random formulas that we need in this proof.

Let $L$ be an integer with $a\log n\leq L\leq b\log n$. First, we are going to
fix $S\subseteq V$ with $\lvert S\rvert=\rho$ and study the event
$\mathcal{F}$ described in the statement. For $c\in\mathcal{C}$ and
$Z\in\mathcal{Z}(c,L)$, we denote by $\mathcal{E}_{1}(Z,S)$ the event that
$Z\subseteq\mathcal{C}^{\Lambda}$, where $\Lambda$ is drawn from
${\left.\kern-1.2pt\mu\right|_{V\setminus S}}$, see Definition 7. Recall that
$Z\subseteq\mathcal{C}^{\Lambda}$ means that none of the clauses in $Z$ are
satisfied by the assignment $\Lambda$ (Definition 5). We note that
$\mathcal{F}=\bigcup_{c\in\mathcal{C},Z\in\mathcal{Z}(c,L)}\mathcal{E}_{1}(Z,S)$.
We are going to show that, for large enough $n$,

$\operatorname{Pr}_{S\sim\tau}\left(\
\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\bigcup\nolimits_{c\in\mathcal{C},Z\in\mathcal{Z}(c,L)}\mathcal{E}_{1}(Z,S)\right)>2^{-\delta
kL}\ \right)\leq 2^{-\delta kL},$ (16)

which is equivalent to the result stated in this lemma. We note that the left-
hand side of (16) can be upper bounded by

$\displaystyle\operatorname{Pr}_{S\sim\tau}\left(\exists
c\in\mathcal{C},Z\in\mathcal{Z}(c,L):\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)>\frac{2^{-\delta
kL}}{\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert}\right)\leq$
(17)
$\displaystyle\sum_{c\in\mathcal{C},Z\in\mathcal{Z}(c,L)}\operatorname{Pr}_{S\sim\tau}\left(\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)>\frac{2^{-\delta
kL}}{\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert}\right).$

We are going to show that, for any $c\in\mathcal{C}$ and
$Z\in\mathcal{Z}(c,L)$,

$\operatorname{Pr}_{S\sim\tau}\left(\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)>\frac{2^{-\delta
kL}}{\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert}\right)\leq\left(2ek\cdot
2^{-(r_{0}-\delta)k}\right)^{L}.$ (18)

Before proving (18), let us complete the proof assuming that this inequality
holds. Recall that $\alpha\leq 2^{rk}$ and that, in the first line of this
proof, we chose $k_{0}$ large enough so that $2^{kr}\leq
2^{(r_{0}-3\delta)k}/(18ek^{3})$. Hence, in light of (15), we have
$\lvert\mathcal{Z}(c,L)\rvert\leq(2^{(r_{0}-3\delta)k}/(2ek))^{L}$. We use the
following observation,

$\text{for }k>1/(\delta\log 2)\text{ and for large enough }n\text{, }\ \
\lvert\mathcal{C}\rvert\leq n\alpha\leq n^{\delta 2k^{5}\log 2}\leq 2^{\delta
kL}.$ (19)

Combining (17), (18) and (19), we conclude the left-hand size of (16) is
bounded above by

$\sum_{c\in\mathcal{C},Z\in\mathcal{Z}(c,L)}\left(2ek\cdot
2^{-(r_{0}-\delta)k}\right)^{L}\leq
n\alpha\cdot\left(\frac{2^{(r_{0}-3\delta)k}}{2ek}\right)^{L}\cdot\left(2ek\cdot
2^{-(r_{0}-\delta)k}\right)^{L}=n\alpha 2^{-2\delta kL}\leq 2^{-\delta kL},$

which completes the proof of (16), and hence the proof of the lemma, subject
to (18).

To prove (18), we are going to find many $S$ for which
$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}(\mathcal{E}_{1}(Z,S))\leq 2^{-\delta
kL}/(\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert)$ holds. With
this in mind, we introduce an event that may occur when sampling $S$:

$\displaystyle\mathcal{E}_{2}(Z):=$ $\displaystyle``\text{the random set
}S\subseteq V\text{ that we select contains fewer}$ (20)
$\displaystyle\text{than }\ell:=\lceil\lvert\operatorname{var}(Z)\cap
V\rvert/k\rceil\text{ variables in }\operatorname{var}(Z)\cap V".$

We will show (in equation (24)) that the event $\mathcal{E}_{2}(Z)$ holds for
most choices of $S$. Before proving this claim, let us assume that
$\mathcal{E}_{2}(Z)$ holds for $S$ and let us prove that
$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}(\mathcal{E}_{1}(Z,S))\leq 2^{-\delta
kL}/(\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert)$. If there are
$c_{1},c_{2}\in Z$ and
$v\in\operatorname{var}(c_{1})\cap\operatorname{var}(c_{2})\cap(V\setminus S)$
such that $c_{1}\neq c_{2}$ and the literal of $v$ in $c_{1}$ is the negation
of the literal of $v$ in $c_{2}$, then at least one of $c_{1}$ and $c_{2}$ is
satisfied by the assignment $\Lambda\colon V\setminus
S\to\\{\mathsf{F},\mathsf{T}\\}$. In this case we have
$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}(\mathcal{E}_{1}(Z,S))=0$. Let us now consider the complementary case:

for all $c_{1},c_{2}\in Z$ with $c_{1}\neq c_{2}$ and
$v\in\operatorname{var}(c_{1})\cap\operatorname{var}(c_{2})\cap(V\setminus
S)$, (21) the literal of $v$ in $c_{1}$ is the same as the literal of $v$ in
$c_{2}$.

In this setting, we call $\omega(v)$ the value of $v$ that does not satisfy
the clauses in $Z$ that contain $v$. Note that $\omega(v)$ is well-defined by
assumption (21). Let $u_{1},u_{2},\ldots,u_{t}$ be the list of variables in
$(\operatorname{var}(Z)\cap V)\setminus S$. We denote by $\mathcal{W}_{j}$ the
event that $u_{j}$ is assigned the value $\omega(u_{j})$ by $\Lambda$ when
sampling $\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus S}}$. Then, by
definition of $\mathcal{W}_{j}$, we have

$\displaystyle\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)$
$\displaystyle=\prod_{j=1}^{t}\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{W}_{j}\left|\
\bigcap\nolimits_{i=1}^{j-1}\mathcal{W}_{i}\right.\right).$

As $\mu$ is $(1/k)$-uniform, we find that
$\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}(\mathcal{W}_{j}|\
\bigcap\nolimits_{i=1}^{j-1}\mathcal{W}_{i})\leq(1/2)\exp(1/k)$ for all
$j\in\\{1,2,\ldots,t\\}$. We conclude that

$\displaystyle\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)$
$\displaystyle\leq\left(\frac{1}{2}\exp\big{(}\frac{1}{k}\big{)}\right)^{t}.$

From (14) and the fact that $\mathcal{E}_{2}(Z)$ holds for $S$, we have

$t=\lvert\operatorname{var}(Z)\cap(V\setminus
S)\rvert\geq\lvert\operatorname{var}(Z)\cap
V\rvert-\lceil\lvert\operatorname{var}(Z)\cap
V\rvert/k\rceil\geq\lvert\operatorname{var}(Z)\cap
V\rvert(1-1/k)-1\geq(r_{0}-\delta)L(k-1)-1.$

It follows that

$\displaystyle\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)$
$\displaystyle\leq\left(\frac{1}{2}\exp\Big{(}\frac{1}{k}\Big{)}\right)^{(r_{0}-\delta)(k-1)L-1}$
$\displaystyle\leq 2\left(2\cdot
2^{-(r_{0}-\delta)k}\exp\Big{(}\frac{(r_{0}-\delta)(k-1)}{k}\Big{)}\right)^{L}$
$\displaystyle\leq\left(4e\cdot 2^{-(r_{0}-\delta)k}\right)^{L},$

where we used that $1/2\leq(1/2)\exp(1/k)<1$ in the second and third
inequality. As $\alpha\leq 2^{rk}\leq 2^{(r_{0}-3\delta)k}/(18ek^{3})\leq
2^{(r_{0}-3\delta)k}/(9\cdot 4ek^{2})$ by hypothesis and (13), we find that

$\left(4e\cdot 2^{-(r_{0}-\delta)k}\right)^{L}=\left(\frac{9\cdot
4ek^{2}\cdot\alpha\cdot
2^{-(r_{0}-\delta)k}}{9k^{2}\alpha}\right)^{L}\leq\left(\frac{2^{-2\delta
k}}{9k^{2}\alpha}\right)^{L}\leq\frac{2^{-2\delta
kL}}{\lvert\mathcal{Z}(c,L)\rvert}\leq\frac{2^{-\delta
kL}}{\lvert\mathcal{C}\rvert\cdot\mathcal{Z}(c,L)\rvert},$ (22)

where in the second to last inequality we applied the bound on the size of
$\mathcal{Z}(c,L)$ given in (15), and in the last inequality we used (19). As
$S$ was picked as any subset of $V$ with $\lvert S\rvert=\rho$ such that
$\mathcal{E}_{2}(Z)$ holds, it follows that

$\operatorname{Pr}_{S\sim\tau}\left(\operatorname{Pr}_{\Lambda\sim{\left.\kern-1.2pt\mu\right|_{V\setminus
S}}}\left(\mathcal{E}_{1}(Z,S)\right)>\frac{2^{-\delta
kL}}{\lvert\mathcal{C}\rvert\cdot\lvert\mathcal{Z}(c,L)\rvert}\right)\leq\operatorname{Pr}_{S\sim\tau}\left(\overline{\mathcal{E}_{2}(Z)}\right).$
(23)

In order to prove (18), which finishes the proof, we need to show
$\operatorname{Pr}_{S\sim\tau}\left(\overline{\mathcal{E}_{2}(Z)}\right)\leq(2ek\cdot
2^{-(r_{0}-\delta)k})^{L}$. The probability of $\overline{\mathcal{E}_{2}(Z)}$
can be bounded as follows. Recall that $\lvert S\rvert=\rho$. If $\rho<\ell$,
then, by the definition of $\mathcal{E}_{2}(Z)$ in (20), we obtain
$\operatorname{Pr}_{S\sim\tau}(\mathcal{E}_{2}(Z))=1$. Otherwise, the number
of choices of $S$ (with $\lvert S\rvert=\rho$) such that $\lvert
S\cap\operatorname{var}(Z)\cap V\rvert\geq\ell$ is at most
$\binom{\lvert\operatorname{var}(Z)\cap V\rvert}{\ell}\binom{\lvert
V\rvert-\ell}{\rho-\ell}$. Hence, we have

$\displaystyle\operatorname{Pr}_{S\sim\tau}\left(\overline{\mathcal{E}_{2}(Z)}\right)$
$\displaystyle\leq\binom{\lvert
V\rvert}{\rho}^{-1}\binom{\lvert\operatorname{var}(Z)\cap
V\rvert}{\ell}\binom{\lvert V\rvert-\ell}{\rho-\ell}$
$\displaystyle=\frac{\rho(\rho-1)\cdots(\rho-\ell+1)}{\lvert V\rvert(\lvert
V\rvert-1)\cdots(\lvert V\rvert-\ell+1)}\binom{\lvert\operatorname{var}(Z)\cap
V\rvert}{\ell}$ $\displaystyle\leq\left(\frac{\rho}{\lvert
V\rvert}\right)^{\ell}\left(\frac{e\lvert\operatorname{var}(Z)\cap
V\rvert}{\ell}\right)^{\ell}\leq\left(\frac{\rho}{\lvert
V\rvert}ek\right)^{\ell},$

where we used $\ell:=\lceil\lvert\operatorname{var}(Z)\cap
V\rvert/k\rceil\geq\lvert\operatorname{var}(Z)\cap V\rvert/k$,
$(p-i)/(q-i)\leq p/q$ for any $0<i<p<q$ and $\binom{p}{q}\leq(ep/q)^{q}$.
Combining this with the hypothesis $\rho\leq\lvert V\rvert/2^{k}$ and the
bound $\ell\geq(r_{0}-\delta)L$, see (14), we obtain

$\operatorname{Pr}_{S\sim\tau}\left(\overline{\mathcal{E}_{2}(Z)}\right)\leq\left(ek2^{-k}\right)^{\ell}\leq\left((ek)^{r_{0}-\delta}\cdot
2^{-(r_{0}-\delta)k}\right)^{L}\leq\left(2ek\cdot
2^{-(r_{0}-\delta)k}\right)^{L}.$ (24)

The bound (18) follows from combining (23) and (24), which completes the
proof. ∎

##  7 Sampling from small connected components

In this section we prove Lemma 14. Recall that Lemma 14 claims the existence
of a procedure to sample from marginals of the uniform distribution on the
satisfying assignments of $\Phi^{\Lambda}$ when the connected components of
$G_{\Phi^{\Lambda}}$ have small size. Here we make this procedure explicit.
Our algorithm exploits the fact that the tree-excess of logarithmic-sized
subsets of $G_{\Phi}$ is bounded by a constant depending only on $k$, see
Lemma 24, and the fact that when $G_{\Phi}$ is acyclic, we can exactly count
and sample satisfying assignments efficiently (Proposition 28).

######  Proposition 28.

There is an algorithm that, for any $k$-CNF formula
$\Phi=(\mathcal{V},\mathcal{C})$ such that $G_{\Phi}$ is a tree, computes the
number of satisfying assignments of $\Phi$ in time
$O(4^{k}\lvert\mathcal{C}\rvert)$.

###### Proof.

We give an algorithm based on dynamic programming. Let us fix a vertex /
clause $c$ of $G_{\Phi}$ as the root and consider the corresponding directed
tree structure $T:=(G_{\Phi},c)$. For any clause $c^{\prime}$ of $\Phi$, let
$T_{c^{\prime}}$ be the subtree of $T$ hanging from $c^{\prime}$. For any
assignment
$\sigma\colon\operatorname{var}(c^{\prime})\to\\{\mathsf{F},\mathsf{T}\\}$,
let $\operatorname{sa}(c^{\prime},\sigma)$ denote the number of satisfying
assignments of the formula determined by $T_{c^{\prime}}$ that extend
$\sigma$. Our goal is computing the number of satisfying assignments of
$\Phi$, which, under this notation, is equal to

$\operatorname{sa}(\Phi):=\sum_{\sigma\colon\operatorname{var}(c)\to\\{\mathsf{F},\mathsf{T}\\}}\operatorname{sa}(c,\sigma).$
(25)

We do this by computing $\operatorname{sa}(c^{\prime},\sigma)$ for any clause
$c^{\prime}$ and any assignment
$\sigma\colon\operatorname{var}(c^{\prime})\to\\{\mathsf{F},\mathsf{T}\\}$.
Using the tree structure of $T$, we show that
$\operatorname{sa}(c^{\prime},\sigma)$ satisfies a recurrence. There are two
cases:

  1. 1.

$c^{\prime}$ is a leaf. Then $\operatorname{sa}(c^{\prime},\sigma)=1$ if
$c^{\prime}$ is satisfied by $\sigma$ and $0$ otherwise.

  2. 2.

$c^{\prime}$ is not a leaf. Let $T_{1},\ldots,T_{l}$ be the trees hanging from
$c^{\prime}$ in $T$ and let $c_{1},\ldots,c_{l}$ be their roots. Then, since
$T_{1},\ldots,T_{l}$ do not share variables as $G_{\Phi}$ is acyclic, we have

$\operatorname{sa}(c^{\prime},\sigma)=\prod_{j=1}^{l}\sum_{\ \ \tau\in
A(c_{j},\sigma)}\operatorname{sa}(c_{j},\tau),$

where $A(c_{j},\sigma)$ is the set of assignments of the variables in
$\operatorname{var}(c_{j})$ that agree with $\sigma$ on
$\operatorname{var}(c^{\prime})\cap\operatorname{var}(c_{j})$.

We can apply this recurrence with dynamic programming to compute
$\operatorname{sa}(c,\sigma)$ for any assignment
$\sigma\colon\operatorname{var}(c)\to\\{\mathsf{F},\mathsf{T}\\}$. More
explicitly, we compute $\operatorname{sa}(c^{\prime},\sigma)$ by levels of the
tree, starting from the deepest level, where all nodes are leaves, and ending
at the root $c$. This involves computing at most $2^{k}$ entries
$\operatorname{sa}(c^{\prime},\cdot)$ per clause $c^{\prime}$ of $\Phi$. After
computing all the entries appearing in this recurrence, we compute the number
of satisfying assignments of $\Phi$, $\operatorname{sa}(\Phi)$, as in equation
(25). The overall procedure takes at most $O(4^{k}\lvert\mathcal{C}\rvert)$
steps since each entry $\operatorname{sa}(c^{\prime},\sigma)$ is accessed at
most $2^{k}$ times when computing the corresponding entries for the parent of
$c^{\prime}$, and there are at most $2^{k}\lvert\mathcal{C}(T)\rvert$ entries.
∎

In Algorithm 3 we give an algorithm based on Proposition 28 to count
satisfying assignments of a $k$-CNF formula. Recall the folklore fact that if
we can count satisfying assignments then we can sample from the marginal of
$\mu_{\Omega}$ on $v$ by counting the satisfying assignments of
$\Phi^{v\mapsto\mathsf{F}}$ and $\Phi^{v\mapsto\mathsf{T}}$.

0: a $k$-CNF formula $\Phi=(\mathcal{V},\mathcal{C})$

0: The number of satisfying assignments of $\Phi$.

Find a spanning forest $T$ of $G_{\Phi}$.

Let $\mathcal{V}_{T}$ be the set of variables that gives rise to edges of
$G_{\Phi}$ that are not in $T$.

$count\leftarrow 0$.

for all $\Lambda\colon\mathcal{V}_{T}\to\\{\mathsf{F},\mathsf{T}\\}$ do

Note that the graph $G_{\Phi^{\Lambda}}$ is acyclic. Hence, we can count the
number of satisfying assignments of $\Phi^{\Lambda}$ in time
$O(4^{k}\lvert\mathcal{C}(\Phi^{\Lambda})\rvert)$ by applying Proposition 28
to each connected component of $G_{\Phi^{\Lambda}}$ and taking the product of
the numbers obtained. Let $\operatorname{sa}(\Phi^{\Lambda})$ be the result of
this computation.

$count\leftarrow count+\operatorname{sa}(\Phi^{\Lambda})$.

end for

return $count$

Algorithm 3 Counting satisfying assignments via trees

######  Proposition 29.

Let $\Phi=(\mathcal{V},\mathcal{C})$ be a $k$-CNF formula and let $c$ be the
tree-excess of $G_{\Phi}$. Then Algorithm 3 counts the number of satisfying
assignments of $\Phi$ in time $O(2^{k(c+2)}\lvert\mathcal{C}\rvert)$.

###### Proof.

We note that, in the execution of Algorithm 3, we have
$\lvert\mathcal{V}_{T}\rvert\leq kc$. Hence, there are at most $2^{kc}$
iterations of the for loop and each one takes
$O(4^{k}\lvert\mathcal{C}\rvert)$ steps, so the running time follows. The fact
that the algorithm is correct follows from the correctness of the procedure
presented in Proposition 28. ∎

Even though the running time of Algorithm 3 is not polynomial in the size of
the formula $\Phi$ (in fact, it is exponential in general), we obtain linear
running time when the formulas considered have constant tree-excess. As shown
in Lemma 24, this is the case for logarithmic-sized subsets of clauses of
random formulas. We can now finish the proof of Lemma 14.

######  Lemma 14.

There is an integer $k_{0}\geq 3$ such that, for any integers $k\geq k_{0}$,
$\xi\geq 1$ and any density $\alpha\leq 2^{rk}$, the following holds w.h.p.
over the choice of $\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$. Let $V$ be a
subset of variables and let $\Lambda\colon V\to\\{\mathsf{F},\mathsf{T}\\}$ be
a partial assignment such that all the connected components in
$G_{\Phi^{\Lambda}}$ have size at most $2k^{4}(1+\xi)\log(n)$. Then, there is
an algorithm that, for any $S\subseteq\mathcal{V}\setminus V$, samples an
assignment from ${\left.\kern-1.2pt\mu_{\Omega^{\Lambda}}\right|_{S}}$ in time
$O(\lvert S\rvert\log n)$.

###### Proof.

We apply Lemma 24 with $b=2k^{4}(\xi+1)$, so, w.h.p. over the choice of
$\Phi=\Phi(k,n,\lfloor\alpha n\rfloor)$, any connected set of clauses in
$G_{\Phi}$ with size at most $b\log(n)$ has tree-excess at most
$c=\max\\{1,2b\log(e\alpha k^{2})\\}=O(1)$. First, we give an algorithm for
the case $\lvert S\rvert=1$. Let $\Phi$, $V$ and $\Lambda$ as in the
statement, and let $S=\\{v\\}$. Let $H$ be the connected component of the
clauses that contain $v$ in $G_{\Phi^{\Lambda}}$, and let
$\Phi^{\prime}=(\mathcal{V}^{\prime},\mathcal{C}^{\prime})$ be the subformula
of $\Phi^{\Lambda}$ with $G_{\Phi^{\prime}}=H$. The formula $\Phi^{\prime}$
has size at most $b\log(n)$. Moreover, the graph $G_{\Phi^{\prime}}=H$ has
tree-excess at most $c$ as $H$ is a subgraph of $G_{\Phi}$ with size at most
$b\log(n)$. Thus, we can apply Proposition 29 to count the number of
satisfying assignments of $\Phi^{\prime v\to\mathsf{F}}$ and $\Phi^{\prime
v\to\mathsf{T}}$ in time $O(2^{k(c+2)}\lvert\mathcal{C}^{\prime}\rvert)=O(\log
n)$. Let these numbers be $t_{0}$ and $t_{1}$ respectively. It is
straightforward to use $t_{0}$ and $t_{1}$ to sample from the marginal of the
distribution $\mu_{\Omega^{\Lambda}}$ for $v$; we only have to sample an
integer $t\in[0,t_{0}+t_{1})$ and output $\mathsf{F}$ if $t<t_{0}$ and
$\mathsf{T}$ otherwise. The whole process takes time $O(\log n)$.

Finally, we argue how to extend this algorithm to the case $\lvert S\rvert>1$.
For this, first, we give an order to the variables in $S$, say
$u_{1},u_{2},\ldots,u_{\ell}$. We then call the algorithm described in the
paragraph above once for each variable in $u_{1},u_{2},\ldots,u_{\ell}$. The
inputs of the algorithm in the $j$-th call are the variable $u_{j}$ and the
assignment $\Lambda_{j}=\Lambda\cup\tau_{j-1}$, where $\tau_{j-1}$ is the
assignment obtained in the previous calls for $u_{1},\ldots,u_{j-1}$. After
this process, $\tau_{\ell}$ is an assignment of all the variables in $S$ that
follows the distribution
${\left.\kern-1.2pt\mu_{\Omega^{\Lambda}}\right|_{S}}$. This assignment has
been computed in $O(\lvert S\rvert\log n)$ steps as we wanted. ∎

##  8 Mixing time of the Markov chain

In this section we study the mixing time of the $\rho$-uniform-block Glauber
dynamics on the marked variables and prove Lemma 11. As explained in Section
2.2, in order to conclude rapid mixing of this Markov chain we apply the
spectral independence framework, which has recently been extended to the
$\rho$-uniform-block Glauber dynamics [8]. Traditionally in path coupling or
spectral independence arguments one has to bound a sum of influences by a
constant in order to obtain rapid mixing of the single-site Glauber dynamics.
However, due to the presence of high-degree variables, an $O(1)$ upper bound
seems unattainable in the random $k$-SAT formula setting; in the worst case
paths of high-degree variable may significantly affect influences. This seems
also to be the case for other random models, such as the hardcore model on
random graphs [5]. Here we show that that sums of influences are at most
$\varepsilon\log n$ for small $\varepsilon$ (Lemma 10). Even though this is
generally not enough to conclude rapid mixing of the single-site Glauber
dynamics, it turns out to be enough to conclude rapid mixing of the
$\rho$-uniform-block Glauber dynamics for $\rho=\Theta(n)$. This section is
divided as follows. In Section 8.1, we explain why bounded-degree methods to
bound the mixing time of the Glauber dynamics fail to generalise from the
bounded-degree $k$-SAT model to the random $k$-SAT model. In Section 8.2 we
prove Lemmas 38 and 10. In Section 8.3 we prove Lemma 11.

###  8.1 Previous work on the Glauber dynamics for bounded-degree $k$-SAT
formulas

In this section we explain why previously known arguments for showing rapid
mixing of the Glauber dynamics on bounded-degree $k$-SAT formulas do not
extend to the random $k$-SAT model. This section is not used in our work and
may be skipped by a reader who just wants to understand our approach and
result. The best result currently known on bounded-degree formulas is [26],
where the authors show, for large enough $k$, how to efficiently sample
satisfying assignments of $k$-CNF formulas in which their variables have
maximum degree $\hat{\Delta}\leq C\,2^{0.1742\cdot k}/k^{3}$, where $C>0$ is a
constant that does not depend on $k$.111In [26] the maximum degree
$\hat{\Delta}$ of $\Phi$ is defined as the maximum over $c\in\mathcal{C}$ of
the number of clauses that share a variable with $c$. Under this definition of
$\hat{\Delta}$, their result holds for $\hat{\Delta}\leq C2^{0.1742\cdot
k}/k^{2}$. Their result actually holds in the more general setting of atomic
constrain satisfaction problems (albeit with a different bound on
$\hat{\Delta}$). As part of their work, they show that the single-site Glauber
dynamics on a set of marked variables mixes quickly. Their argument is
restricted to atomic CSPs with bounded-degree and strongly exploits the
properties of the Glauber dynamics in this setting. They study the optimal
coupling of the single-site Glauber dynamics, we refer to [31] for the
definition of coupling of Markov chains. In such a coupling the goal is to
show that two copies of the chain starting from truth assignments differing in
at least a marked variable (a so-called discrepancy) can be coupled in a small
number of steps. Here it is crucial that the marginals of the marked variables
are near $1/2$, so the optimal coupling generates new discrepancies with small
probability. At this stage, the high-level idea to conclude rapid mixing of
the Glauber dynamics is bounding the probability that the dynamics has not
coupled by a product of probabilities, each corresponding to the event that a
clause is unsatisfied at a certain time, and aggregating over all possible
discrepancy sequences.

The fundamental observation in [26], based on the work on monotone $k$-CNF
formulas presented in [24], is that if there is an update of a marked variable
that generates a discrepancy in the chains, then there is another marked
variable where the chains disagree that is connected to the former variable
through a path of clauses, where consecutive clauses in the path share at
least a variable. Moreover, each one of the clauses in this path is
unsatisfied by at least one of the two copies of the chain. As a consequence,
from a discrepancy at time $t$ one can find a sequence of discrepancies going
back to time $0$, and these discrepancies are joined by a path of clauses.
Thus, the union bound over discrepancy sequences is essentially a union bound
over paths of clauses with a particular time structure, where the same clause
can be appear in the path several times. Extending this idea to the random
$k$-SAT model presents two main issues. First of all, the number of
discrepancy sequences of any given length may be too large due to the presence
of bad clauses and the fact that they can repeatedly appear in the sequence.
Moreover, it may be the case that these discrepancy sequences mostly consist
of bad clauses, which are always unsatisfied in both chains and, thus, the
probability that they are unsatisfied is not small. Interestingly, similar
issues arise when directly extending the bounded-degree approach based on the
coupling process of [32, 18] to our setting. In [18] the mixing time argument
only succeeds when $\hat{\Delta}\leq 2^{k/20}/(8k)$ and is also based on a
union bound over path of clauses that are unsatisfied or contain discrepancies
after running a coupling process. However, very importantly, these paths of
clauses are simple (clauses are not repeated) and the combinatorial structures
appearing in the coupling process are less complex than the discrepancy
sequences of [26]. This allowed the authors of [21] to exploit the expansion
properties of random $k$-CNF formulas to analyse the coupling process of [32]
on the random setting. Here we incorporate some novel ideas to the work of
[21] in order to obtain a tighter analysis that leads to nearly linear running
time of our sampling algorithm.

###  8.2 Spectral independence in the $k$-SAT model

In this section we prove Lemma 10. In order to bound the sum of influences of
marked variables, we follow the coupling process technique that is standard in
the literature [21, 32, 18]. In this work we introduce the concept of
auxiliary variables in the coupling process and exploit the sparsity
properties of logarithmic-sized sets of clauses, which allows us to conclude a
$2^{-r_{0}k}\log n$ spectral independence bound. The key idea is that if we
progressively extend two assignments $X$ and $Y$ on auxiliary variables
following the optimal coupling, at some point the formulas $\Phi^{X}$ and
$\Phi^{Y}$ factorise in small connected components in spite of the presence of
bad variables and, on top of that, $\Phi^{X}$ and $\Phi^{Y}$ share most of
these connected components. Then we can bound influences between marked
variables by analysing the connected components where $\Phi^{X}$ and
$\Phi^{Y}$ differ. First, let us introduce some notation.

Let $\mu$ and $\nu$ be two distributions over the same space
$\widehat{\Omega}$. A coupling $\tau$ of $\mu$ and $\nu$ is a joint
distribution over $\widehat{\Omega}\times\widehat{\Omega}$ such that the
projection of $\tau$ on the first coordinate is $\mu$ and the projection on
the second coordinate is $\nu$. Recall that the total variation distance of
$\mu$ and $\nu$ is defined by
$d_{\mathrm{TV}}(\mu,\nu)=\frac{1}{2}\sum_{x\in\widehat{\Omega}}\lvert\mu(x)-\nu(x)\rvert$.
If a random variable $X$ has distribution $\mu$, we also write
$d_{\mathrm{TV}}(X,\nu)$ to mean $d_{\mathrm{TV}}(\mu,\nu)$.

######  Proposition 30 (Coupling lemma).

Let $\tau$ be a coupling of $\mu$ and $\nu$. Then
$d_{TV}(\mu,\nu)\leq\operatorname{Pr}_{(X,Y)\sim\tau}(X\neq Y)$. Moreover,
there exists a coupling that achieves equality.

The coupling $\tau$ of $\mu$ and $\nu$ that minimises
$\operatorname{Pr}_{(X,Y)\sim\tau}(X\neq Y)$ is called _optimal_. Let us now
assume that $\mu$ and $\nu$ are Bernoulli distributions with parameters $0\leq
p\leq q\leq 1$ respectively, so $\operatorname{Pr}_{\mu}(X=1)=p$ and
$\operatorname{Pr}_{\nu}(Y=1)=q$. The _monotone coupling_ $\tau$ of $\mu$ and
$\nu$ is defined as follows. We pick $U$ uniformly at random in $[0,1]$ and
set $X=1$ only when $U\leq p$ and $Y=1$ only when $U\leq q$. For this coupling
we have $\operatorname{Pr}_{(X,Y)\sim\tau}(X\neq Y)=q-p=d_{\mathrm{TV}}(X,Y)$
and, hence, the monotone coupling is optimal.

Before presenting our coupling process, we show how we can bound a sum of
influences between marked variables with the help of the coupling lemma. In
all this section we fix a $k$-CNF formula $\Phi$ and a $r_{0}$-marking
$(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$
of $\Phi$. Given two assignments $\Lambda_{1}$ and $\Lambda_{2}$ on disjoint
sets of variables, we denote by $\Lambda_{1}\cup\Lambda_{2}$ the combined
assignment on the union of their domains.

######  Proposition 31.

Let $u\in\mathcal{V}_{\mathrm{m}}$ and $\Lambda\colon
S\to\\{\mathsf{F},\mathsf{T}\\}$ with
$S\subseteq\mathcal{V}_{\mathrm{m}}\setminus\\{u\\}$. Let $(X,Y)$ be a
coupling where $X$ follows the distribution
${\left.\kern-1.2pt\mu_{\Omega^{\Lambda\cup
u\mapsto\mathsf{T}}}\right|_{\mathcal{V}_{\mathrm{m}}}}$ and $Y$ follows the
distribution ${\left.\kern-1.2pt\mu_{\Omega^{\Lambda\cup
u\mapsto\mathsf{F}}}\right|_{\mathcal{V}_{\mathrm{m}}}}$. Then

$\sum_{v\in\mathcal{V}_{\mathrm{m}}\setminus(S\cup\\{u\\})}\left|\mathcal{I}^{\Lambda}(u\to
v)\right|\leq\sum_{v\in\mathcal{V}_{\mathrm{m}}\setminus(S\cup\\{u\\})}\operatorname{Pr}\left(X(v)\neq
Y(v)\right).$ (26)

###### Proof.

Let $v\in\mathcal{V}_{\mathrm{m}}$. Then for any
$\omega\in\\{\mathsf{F},\mathsf{T}\\}$, we have
$\operatorname{Pr}(v\mapsto\omega|\Lambda,u\mapsto\mathsf{T})=\operatorname{Pr}(X(v)=\omega)$
and
$\operatorname{Pr}(v\mapsto\omega|\Lambda,u\mapsto\mathsf{F})=\operatorname{Pr}(Y(v)=\omega)$.
Thus, by the coupling lemma,

$\left|\mathcal{I}^{\Lambda}(u\to
v)\right|=\left|\operatorname{Pr}(X(v)=\mathsf{T})-\operatorname{Pr}(Y(v)=\mathsf{T})\right|=d_{TV}(X(v),Y(v))\leq\operatorname{Pr}\left(X(v)\neq
Y(v)\right),$

and the proof follows by adding over
$v\in\mathcal{V}_{\mathrm{m}}\setminus(S\cup\\{u\\})$. ∎

For two assignments $X$ and $Y$ on a subset of variables $V$, we say that $X$
and $Y$ have a _discrepancy_ at $v\in V$ when $X(v)\neq Y(v)$. In [18] the
authors manage to bound (26) by a constant that does not depend on $n$ when
the considered formula has bounded degree. However, their argument breaks
under the presence of high-degree variables due to the fact that we cannot
control the number of bad clauses in a path of clauses unless the path has
length at least $\Omega(\log n)$. Here instead we perform the coupling process
developed in [21] over auxiliary variables, which accounts for the presence of
bad clauses.

Before presenting our algorithm for the coupling process on auxiliary
variables, let us describe some of the notation and structures that are used
in this algorithm. Let $u\in\mathcal{V}_{\mathrm{m}}$ and $\Lambda\colon
S\to\\{\mathsf{F},\mathsf{T}\\}$ with
$S\subseteq\mathcal{V}_{\mathrm{m}}\setminus\\{u\\}$. We start with two
assignments $\widehat{X}$ and $\widehat{Y}$ that have a discrepancy at $u$ and
agree with $\Lambda$ on $S$. In the coupling process we identify a set of
failed clauses, denoted
$\mathcal{F}_{\mathrm{d}}\cup\mathcal{F}_{\mathrm{u}}$. At each step of the
process, we check if a clause is failed or extend the coupling to an auxiliary
variable. It is important in our arguments that all clauses containing a
discrepancy are failed, and that we make sure that the set of failed clauses
is connected in $G_{\Phi}$ at all times. In order to achieve connectivity of
failed clauses, at each step of the coupling process we only consider clauses
that are adjacent to failed clauses in $G_{\Phi}$. For ease of reading, here
we present a list of the structures that appear in our algorithm.

  1. 1.

$\mathcal{V}_{\mathrm{d}}$. Set of discrepancies, i.e., variables $v$ with
$\widehat{X}(v)\neq\widehat{Y}(v)$.

  2. 2.

$\mathcal{F}_{\mathrm{d}}$. Set of all clauses containing a variable in
$\mathcal{V}_{\mathrm{d}}$. These are failed clauses.

  3. 3.

$\mathcal{V}_{\mathrm{set}}$. Set of variables that are assigned a value in
the coupling.

  4. 4.

$\mathcal{F}_{\mathrm{u}}$. Set of clauses that have been considered by the
coupling process, and are either bad or are unsatisfied by at least one of
$\widehat{X}$ and $\widehat{Y}$ and have all their auxiliary variables in
$\mathcal{V}_{\mathrm{set}}$. These are failed clauses.

  5. 5.

$\mathcal{C}_{\mathrm{rem}}$. Set of clauses that have unassigned auxiliary
variables or have not been explored yet.

Our coupling process on auxiliary variables is given in Algorithm 4.

0: A $k$-CNF formula $\Phi=(\mathcal{V},\mathcal{C})$, an $r_{0}$-marking
$\mathcal{M}=(\mathcal{V}_{\mathrm{m}},\mathcal{V}_{\mathrm{a}},\mathcal{V}_{\mathrm{c}})$,
$u\in\mathcal{V}_{\mathrm{m}}$ and $\Lambda\colon
S\to\\{\mathsf{F},\mathsf{T}\\}$ with
$S\subseteq\mathcal{V}_{\mathrm{m}}\setminus\\{u\\}$.

0: a pair of assignments
$\widehat{X},\widehat{Y}\colon\mathcal{V}_{\mathrm{set}}\to\\{\mathsf{F},\mathsf{T}\\}$
for some set of variables $\mathcal{V}_{\mathrm{set}}$ such that: $\circ$
$S\cup\\{u\\}\subseteq\mathcal{V}_{\mathrm{set}}\subseteq
S\cup\\{u\\}\cup\mathcal{V}_{\mathrm{a}}$, $\circ$ $\widehat{X}$ and
$\widehat{Y}$ agree with $\Lambda$ on $S$, $\widehat{X}(u)=\mathsf{T}$ and
$\widehat{Y}(u)=\mathsf{F}$.

We fix two total orders $\leq_{\mathcal{V}}$ and $\leq_{\mathcal{C}}$ over the