Fast sampling of satisfying assignments from random $k$-SAT



Introduction {#sec:intro}
============

The random $k$-SAT model is a foundational model in the study of randomised algorithms. For integers $k \ge 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$ @ding2015 [@coja2016]. 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 @coja2010 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 @AC08.

Lately there has been significant interest in the related computational problem of sampling satisfying assignments of $\Phi$ jessicabrown@example.net. 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$ @2SAT [@AminBelief2; @SlySunZhang; @montanari2007]. 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  @AminBelief2 [@montanari2007; @CR13], the regular $k$-SAT model @coja-oghlan_wormald_2018, and the regular NAE-SAT model @nam2020onestep [@SlySunZhang]. Very recently, a formula for the free energy of the $2$-SAT model was given in @2SAT.

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 $o_k(1)$ @montanari2007. 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 large number of variables are unbounded. Very recently @galanis2019counting 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 @moitra19 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 and to solve 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 solve this open problem by giving 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 \densitymaindef$ for $r = \rmain$, 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 @galanis2019counting. 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 \[sec:intro:techniques\]. Roughly, our Markov chain is a uniform-block Glauber dynamics which, interestingly, mixes quickly in spite of 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, so that we can exploit local sparsity properties of random $k$-SAT.

We say that an event $\mathcal{E}$ regarding the choice of the random formula $\Phi$ holds *with high probability* (abbreviated w.h.p.) if $\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.

\[thm:sampling\]

Let $r := \rmain$. For any real $\theta \in (0,1)$, there is an integer $k_0 \ge 3$ with $k_0 = O(\log(1/\theta) )$ such that, for any integers $k\ge k_0$ and $ \xi \ge 1$, and for any positive real $\alpha \le \densitymaindef$, 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^\theta \, (n/\varepsilon)^2 )$, where $\varepsilon$ is the multiplicative error, see @feng2020 [Section 7] and Remark \[rem:counting\] for details.

Proof outline {#sec:intro:techniques}
=============

\[sec:proof-outline\] \[sec:po\] Following a long tradition in approximate counting, our nearly linear-time sampling algorithm is based on running a Markov chain; typically one runs a Markov chain on the whole state space, but the twist in $k$-SAT is that the state space of the Markov chain needs to be carefully selected. This approach has been recently applied to bounded-degree $k$-CNF formulas @feng2020 [@jain2020; @feng2021; @jain2021sampling] building on the work of Moitra @moitra19 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 SAT solutions, and even ensuring a connected state space is major problem. Working around this is one of the main challenges for us too, and in our random $k$-SAT setting it is further aggravated by the fact that a large number of variables (a linear number of them) have degrees much higher than average. In fact, w.h.p., a good portion of vertices have degrees depending on $n$ — recall that the maximum degree of the formula scales as $(\log n) /( \log \log n)$. This poses several challenges for the Markov chain approach to work. 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 \[sec:po:marking\] 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 @jain2020 [@feng2020], are based on coupling techniques and break under the presence of high-degree variables. We delve into this challenge in Section \[sec:po:si\], where we outline a novel argument that analyses the mixing time of the uniform-block Glauber dynamics using recent advances in spectral independence @AlevLau [@KO20; @alg20; @Chen2020SI]. 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 @alg20 [@Chen2020SI]). 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 this work 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. The full algorithm can be found in Section \[sec:po:alg\]. Before stating our algorithm, we introduce some of the constructions and results that we develop in this work.

Marking variables in the random $k$-SAT model {#sec:po:marking}
---------------------------------------------

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}_m$ of so-called "marked" variables of the random formula, leaving the rest of the variables unassigned. The variables in $\mathcal{V}_m$ are chosen in a way that ensures that their marginals are near $1/2$, which is important for ensuring rapid mixing. Moitra @moitra19 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 @galanis2019counting 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$ 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. With this in mind, we introduce our own notion of high-degree variables and marking. 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.

\[$r$, $r_0$, $\delta$, high-degree, $\Delta$, $\alpha_0$\] \[def:degree\] Let $r := \rmain$, $r_0 := \rvalue$, and $\delta = 0.00001$. Let $k \ge 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 $\mdeg := \mdegdef$. We will consider random $k$-CNF formulas with density at most $\alpha_0 := \densitydef$.

Note that $r$ is the constant from Theorem \[thm:sampling\]. This constant 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 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 $\var(c)$ the set of variables appearing in $c$, and for any $S \subseteq \mathcal{C}$ we denote $\var(S) = \bigcup_{c \in S} \var(c)$.

We refer to Section \[sec:bad\] 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 \[def:degree\]), 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 $\bv$ and $\bc$ to denote the sets of bad variables and clauses. We use $\gv = \mathcal{V} \setminus \bv$ to denote the set of *good variables*, and $\gc=\mathcal{C} \setminus \bc$ to denote the set of *good clauses*. The following proposition, proved in Section \[sec:bad\], summarises the main properties of the above sets.

\[prop:bad\] <span> Let $\Phi = (\mathcal{V}, \mathcal{C})$ be a $k$-CNF formula. For any $c \in \gc$, we have $\lvert \var(c) \cap \bv \rvert \le 2$, and for any $c \in \bc$, we have $\lvert \var(c) \cap \gv \rvert = 0$. Moreover, every good variable has degree less than $\Delta$. There is a procedure to determine $\bc$ that runs in time $O(n + m k)$, where $n$ is the number of variables of $\Phi$ and $m$ is the number of clauses of $\Phi$. </span>

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 \[lem:bad\] for a precise statement. At this stage, it would be natural to try to rework the Markov chain approach of @feng2020. 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 \[sec:po:si\], 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 influence that the high-degree variables have on the marginal probabilities of other variables. Therefore, we need to develop an approach that is robust against the presence of high-degree variables. Our main contribution is a novel argument to apply the spectral independence framework @Chen2020SI [@Chen2021] to the random $k$-SAT model. In our arguments, it is important to introduce a third type of good variables: *auxiliary variables*. This motivates the following definition of marking.

\[$r$-distributed, $r$-marking\] \[def:distributed-marking\] Let $r \in (0, 1)$. Let $\Phi = (\mathcal{V}, \mathcal{C})$ be a $k$-CNF formula and $V$ be a subset of $\gv$. We say that $V$ is *$r$-distributed* if for each $c \in \gc$ we have $\lvert \var(c) \cap V \rvert \ge r (k-3)$.

An *$r$-marking* of $\Phi$ is a partition $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$ of the variables of $\Phi$ such that

1.  \[item:def-marking:1\] $\mathcal{V}_c$ contains all the bad variables,

2.  \[item:def-marking:2\] the sets of good variables $\mathcal{V}_m$, $\mathcal{V}_a$, and $\mathcal{V}_c \setminus \bv$ are $r$-distributed.

The variables in $\mathcal{V}_m$ are called *marked* variables, the variables in $\mathcal{V}_a$ are called *auxiliary* variables, and the variables in $\mathcal{V}_c$ are called *control* variables.

In Section \[sec:marking\] we show that random $k$-CNF formulas have $r_0$-markings when the density $\alpha$ is below the threshold $\alpha_0 = \densitydef$, 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 \[prop:marginals\] below; first we give some relevant definitions.

\[$\Omega^*$, $\mu_A$, $\Omega$, $\Phi^\Lambda$, $\mathcal{C}^{\Lambda}$, $\mathcal{V}^{\Lambda}$, $\Omega^\Lambda$\] \[def:mu\] \[def:subformula\] 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$.

\[prop:marginals\] <span> There is an integer $k_0$ such that for any $k \ge k_0$ and any density $\alpha$ with $\density \le \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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$. Moreover, for any such marking, for any $v \in \mathcal{V}_m \cup \mathcal{V}_a$, any $V \subseteq \mathcal{V}_m \cup \mathcal{V}_a$ with $v \not \in V$, and any $\Lambda \colon V \to \{\mathsf{F}, \mathsf{T}\}$, we have $$\max \left\{ \pr_{\mu_{\Omega^\Lambda}}\left( v \mapsto \mathsf{F} \right), \pr_{\mu_{\Omega^\Lambda}}\left( v \mapsto \mathsf{T}\right)  \right\} \le \frac{1}{2} \exp\left(\frac{1}{k 2^{\delta k}}\right).$$ </span>

\[prop:marginals:proof\] This follows directly by combining Lemmas \[lem:marking\] and \[lem:marginals\], which are stated and proved in Section \[sec:marking\].

The bound given in Proposition \[prop:marginals\] on the marginal probabilities of the marked and auxiliary variables is exploited several times in our work, and we will highlight 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.

\[${{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V}   }}$\] \[def:marginal\] Let $\mathcal{V}$ be a finite set and let $\Omega \subseteq \{\mathsf{F}, \mathsf{T}\}^{\mathcal{V}}$. Let $\mu$ be a distribution over $\Omega$. We denote by ${{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V}   }}$ the marginal distribution of $\mu$ on a set $V \subseteq \mathcal{V}$.

Proposition \[prop:marginals\] essentially states that the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m \cup \mathcal{V}_a}   }}$ is very close to the uniform distribution over all assignments $\mathcal{V}_m \cup \mathcal{V}_a  \to \{\mathsf{F}, \mathsf{T}\}$. This concept is formalised in the following definition.

\[$\varepsilon$-uniform\] \[def:uniform\] Let $V$ be a set of variables. Let $\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$. When we write $\pr_\mu(\Lambda)$ or $\pr_\mu(\cdot \vert \Lambda)$ we use $\Lambda$ as a placeholder for the event that the variables in $S$ are assigned values according to $\Lambda$ when sampling from $\mu$. Let $\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\{ \pr_{\mu}\left( \left. v \mapsto \mathsf{F} \right| \Lambda\right), \pr_{\mu}\left( \left. v \mapsto \mathsf{T} \right| \Lambda \right)  \right\} \le \frac{1}{2}e^{\varepsilon}.$$

In our setting, the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m}   }}$ is $\epsilon$-uniform for $\epsilon = (2^{-\delta k}/k)$ (Proposition \[prop:marginals\]) so, for any $\Lambda \colon \mathcal{V}_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}_m \rvert}$. The $\epsilon$-uniform property also guarantees that the space of assignments $\Lambda \colon \mathcal{V}_m  \to \{\mathsf{F}, \mathsf{T}\}$ with $\pr_{\mu_\Omega}(\Lambda) > 0$ is connected, so we can indeed consider the Glauber dynamics over $\mathcal{V}_m$. This leads to the main challenge of this work: does this chain mix rapidly?

Mixing time of the Glauber dynamics on the marked variables {#sec:po:si}
-----------------------------------------------------------

Recently, there has been significant progress in showing that the single-site Glauber dynamics on appropriately chosen subsets of variables mixes quickly for $k$-CNF formulas with bounded degree @feng2020 [@jain2021sampling]. 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 more details in Section \[sec:po:si:pw\]. 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 @alg20 [@Chen2020SI; @bez2021] 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 @montanari2007 and therefore, we have to develop a novel 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-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$, is $(\epsilon \log n)$-spectrally independent for some small $\epsilon>0$. Our argument relates the spectral independence condition to the expected size of the connected components of $\Phi^{\Lambda}$ for a random assignment $\Lambda$ of a subset of variables of $\Phi$. This allows us to exploit the local sparsity properties of the random $k$-SAT model to analyse the mixing time of the Glauber dynamics. Unfortunately, the fact that ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$ is $\eta$-spectrally independent for $\eta = \epsilon \log n$ is not enough to conclude rapid mixing of the single-site Glauber dynamics. Hence, in this work we focus our attention on the $\rho$-uniform-block Glauber dynamics with $\rho$ linear in $n$, whose mixing time can be analysed even when $\eta$ is not a constant.

### The $\rho$-uniform-block Glauber dynamics {#sec:po:si:block}

Let $V$ be a finite set of size $M$ and let $\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 \ge 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 \vert \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) \le \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 $\pr_{\mu}(\Lambda) > 0$, and $\omega \in \{\mathsf{F}, \mathsf{T}\}$, it either holds that $\pr_\mu(v \mapsto \omega \vert \Lambda ) = 0$ or $\pr_\mu(v \mapsto \omega \vert \Lambda) \ge b$. Spectral independent results have recently been used in the $b$-marginally bounded setting to obtain fast mixing time of the uniform-block Glauber dynamics @Blanca2022 [@Chen2021]. For $S \subset V$, $\Lambda \colon S \to \{\mathsf{F}, \mathsf{T}\}$ with $\pr_{\mu}(\Lambda) > 0$, and $u,v \in V$ with $u \not \in S$ and $0 < \pr_{\mu}(u \mapsto \mathsf{T} \vert \Lambda) < 1$, we define the *influence* of $u$ on $v$ (under $\mu$ and $\Lambda$) as $$\label{eq:influence}
  \mathcal{I}^{\Lambda}(u \to v) = \pr_\mu\left( v \mapsto \mathsf{T} \vert u \mapsto \mathsf{T}, \Lambda\right) - \pr_\mu\left( v \mapsto \mathsf{T}  \vert u \mapsto \mathsf{F}, \Lambda\right).$$ The *influence matrix conditioned on $\Lambda$* is the matrix ${\mathcal{I}}^\Lambda$. We denote by $\lambda_1({\mathcal{I}}^\Lambda)$ its largest eigenvalue. 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 $\pr_{\mu}(\Lambda) > 0$ we have $\lambda_1({\mathcal{I}}^\Lambda) \le \eta$. Combining some of the results of @Chen2021 one can conclude the following bound for the mixing time of the uniform-block Glauber dynamics, see Appendix \[sec:ap:mt\] for details.

\[lem:block-glauber\] The following holds for any reals $b, \eta > 0$, any $\kappa \in (0,1)$ and any integer $M$ with $M \ge \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) \le \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}_m$, and the set of states coincides with the set of assignments $\mathcal{V}_m \to \{\mathsf{F}, \mathsf{T} \}$ as all of them have positive probability. In this setting, the target distribution is ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$. The distribution ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$ is $(1/e)$-marginally-bounded as a straightforward consequence of the fact that it is $(1/k)$-uniform, see Remark \[rem:marginally-bounded\] 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 @Chen2020SI) that, for $S \subset V$ and $\Lambda \colon S \to \{\mathsf{F}, \mathsf{T}\}$, we have $$\label{eq:si}
    \lambda_1({\mathcal{I}}_\Lambda) \le \max_{u \in V \setminus S} \sum_{v \in V \setminus S} \lvert \mathcal{I}^{\Lambda}(u \to v) \rvert.$$

### Spectral independence in the random $k$-SAT model {#sec:po:si:results}

In this section we show how to establish the spectral independence condition in the random $k$-SAT model. The results stated in this section are proved in Section \[sec:mixing-time\]. Our main technical result in this work is Lemma \[lem:si\].

\[lem:si\] <span> There is an integer $k_0 \ge 3$ such that for any integer $k \ge k_0$ and any density $\alpha$ with $\density \le 2^{rk}$ 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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$, the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m}   }}$ is $(2^{-(\delta/2) k} \log n)$-spectrally independent.</span>

We are going to describe some of the ideas behind the proof of Lemma \[lem:si\]. First, we highlight the fact that, due to the presence of high-degree variables, our techniques seem to be too weak 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 @bez2021, where decay of correlation is exploited to prove $\eta$-spectral independence. In light of Lemma \[lem:block-glauber\], $\eta = O(\log n)$ is good enough for proving polynomial mixing time of the uniform-block Glauber dynamics. However, in order to obtain near optimal mixing time it is important that $\eta = o_k(1) \log n$, as illustrated in the proof of our mixing time result, Lemma \[lem:mixing-time\], which follows from Lemmas \[lem:block-glauber\] and \[lem:si\] after some straightforward calculations, see Section \[sec:mixing-time\] for details.

\[lem:mixing-time\] <span> There is a function $k_0(\theta) = \Theta(\log(1/\theta))$ such that, for any $\theta \in (0,1)$, for any integer $k \ge k_0(\theta)$ and any density $\alpha$ with $\density \le 2^{rk}$ 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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$ and for $\rho = \lceil 2^{-k-1} \lvert \mathcal{V}_m \rvert \rceil$, the $\rho$-uniform-block Glauber dynamics for updating the marked variables has mixing time $T_{mix}(\rho, \varepsilon/2) \le T := \mtdef$.</span>

Lemma \[lem:mixing-time\] is stated for the block size $\rho = \lceil 2^{-k-1} \lvert \mathcal{V}_m \rvert \rceil$, but it could be proved more generally when $\rho = c \lvert \mathcal{V}_m \rvert$ and $c \in (0,1)$. Our result is stated for $\rho = \lceil 2^{-k-1} \lvert \mathcal{V}_m \rvert \rceil$ because the fact that $\rho \le \lvert \mathcal{V}_m \rvert / 2^k$ will be relevant in Section \[sec:po:structure\].

Our approach to prove $\eta$-spectral independence significantly differs from those that one can find in the case of 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; the further away two vertices are in the tree, the smaller the influence that one vertex has in the other. Here we find a novel way to connect influences to the structure of the dependency graph $G_\Phi$ by exploiting auxiliary variables, and we state this connection in Lemma \[lem:expectation\].

\[$G_\Phi$\] \[def:graph-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 $\var(c_1) \cap \var(c_2) \ne \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 \var(c_1)$ and $v \in \var(c_\ell)$.

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.

\[lem:expectation\] <span> There is an integer $k_0 \ge 3$ such that for any integer $k \ge k_0$ and any density $\alpha$ with $\density \le 2^{rk}$ 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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$, the sum of influences between marked variables can be bounded as follows. For any $u \in \mathcal{V}_m$, $S \subseteq \mathcal{V}_m \setminus \{u\}$, and $\Lambda_S \colon S \to \{\mathsf{F}, \mathsf{T}\}$, we have, for $\tau = {{  \left.\kern-\nulldelimiterspace   \mu_{\Omega^{\Lambda_S}}     \right|_{\mathcal{V}_a}   }}$, $$\sum_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S}(u \to v) \right| \le \frac{2}{k 2^{\delta k}} \mathbb{E}_{\Lambda_a \sim \tau} \big[ \left| \{v \in \mathcal{V}_m \setminus S : u\text{ and }v\text{ are connected in }\Phi^{\Lambda_S\cup\Lambda_a} \}\right| \big].$$ </span>

\[Proof sketch\] The full proof can be found in Section \[sec:mixing-time\]. Here we highlight the two key ideas connecting influences and the structure of the random formula $\Phi$, as these ideas illustrate the importance of auxiliary variables in our arguments. The first key observation is that we can expand the influence $\mathcal{I}^{\Lambda_m}(u \to v)$ according to the assignment $\Lambda_a$ on the set of auxiliary variables $\mathcal{V}_a$, that is, $\mathcal{I}^{\Lambda_m}(u \to v)$ is equal to $ \sum_{\Lambda_a \colon \mathcal{V}_a \to \{\mathsf{F}, \mathsf{T}\}} \pr_{\tau} \left( \Lambda_a\right)  \mathcal{I}^{\Lambda_m \cup \Lambda_a}(u \to v)$. Therefore, by the triangle inequality, we obtain the bound $$\begin{aligned}        
      \sum_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_m}(u \to v) \right| & \le \mathbb{E}_{\Lambda_a \sim \tau} \left[ \sum\nolimits_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_m \cup \Lambda_a}(u \to v) \right| \right],  
    \end{aligned}$$ see Section \[sec:mixing-time\] for details. Now we can exploit Proposition \[prop:marginals\] to bound each one of the terms $ \left| \mathcal{I}^{\Lambda_m \cup \Lambda_a}(u \to v) \right|$ by $2/(k2^{\delta k})$ after some calculations. The second key observation is that if $u$ and $v$ are in distinct connected components of $G_{\Phi^\Lambda}$ for $\Lambda = \Lambda_m \cup \Lambda_a$, then $\mathcal{I}^{\Lambda}(u \to v) = 0$. Therefore, we only have to consider a sum over those variables $v \in \mathcal{V}_m \setminus S$ in the same connected component as $u$ in $G_{\Phi^\Lambda}$, yielding the lemma.

We want to bound the expectation given in Lemma \[lem:expectation\] by $(2^{-(\delta/2) k} \log n)$. This raises the following problem, where we can think of $V$ as the set of auxiliary variables and $\mu$ as the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_a}   }}$.

\[prob:si\] Let $\alpha \le 2^{r k}$, let $\Phi = \Phi(k, n, \lfloor \alpha n \rfloor)$ be a random $k$-CNF formula, let $V$ be an $r_0$-distributed subset of variables of $\Phi$ and let $\mu$ be an $(1/k)$-uniform distribution over the assignments on $V$. Does the formula $\Phi$, w.h.p. over the choice of $\Lambda \sim \mu$, break into connected components with size at most $O(\log n)$ when we assign $V$ according to a random assignment $\Lambda \sim \mu$?

We tackle Problem \[prob:si\] in Section \[sec:po:structure\], where in Lemma \[lem:cc-general\] we show that w.h.p., over the choice of $\Lambda \sim \mu$, the connected components of $\Phi^\Lambda$ have size at most $2 k^4 \log n$. This result in combination with Lemma \[lem:expectation\] allow us to prove Lemma \[lem:si\] without much difficulty, see Section \[sec:mixing-time\] for details.

Analysis of the connected components of $\Phi^\Lambda$ {#sec:po:structure}
------------------------------------------------------

In this section we state our results on Problem \[prob:si\]. The results stated in this section are proved in Section \[sec:errors\]. Problem \[prob:si\] turns out to be related to the third challenge mentioned at the beginning of Section \[sec:po\]: 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.

We start by establishing the connection between Problem \[prob:si\] and simulating the $\rho$-uniform-block Glauber dynamics. One of the key ideas to simulate this chain is starting the chain on an assignment $X_0 \colon \mathcal{V}_m \to \{\mathsf{F}, \mathsf{T}\}$ drawn from the uniform distribution over all assignments of $\mathcal{V}_m$. Since the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$ is $(1/k)$-uniform (Proposition \[prop:marginals\]), 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 \[cor:marginals:glauber\]), which will be important.

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}_m$ with $\lvert S \rvert = \rho$ and any assignment $\Lambda \colon \mathcal{V}_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$? Note the similarity between this question and Problem \[prob:si\]. Lemma \[lem:cc-general\] gives a positive answer when $0 \le \rho \le \lvert V\rvert / 2^k$, which solves Problem \[prob:si\] as the particular case $\rho = 0$. Here the reader can see $V$ as the set of marked variables or the set of auxiliary variables depending on the application. The proof of Lemma \[lem:cc-general\] exploits sparsity properties of logarithmic-sized connected sets of clauses in random formulas in conjunction with the fact that $\mu$ is $(1/k)$-uniform.

\[lem:cc-general\]

There is an integer $k_0 \ge 3$ such that, for any integer $k \ge k_0$, any density $\density \le \densitymaindef$, 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 \density n\rfloor)$.

Let $L$ be an integer satisfying $a \log n \le L \le 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 \le \rho \le \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-\nulldelimiterspace   \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 \ge  L$ such that all clauses in $Y$ are unsatisfied by $\Lambda$. Then $
    \pr_{S \sim \tau} \left( \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{F} \right) \le 2^{- \delta k L}  \right) \ge 1 - 2^{-\delta k L}$.

\[Proof sketch\] The proof is in Section \[sec:errors\]. For the sake of exposition, we first sketch the proof in the case $\rho = 0$, where the conclusion in the statement reads $\pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V}   }}} \left( \mathcal{F} \right) \le 2^{- \delta k L}$. At the end of this proof sketch we explain how we extend the proof to any $\rho$ with $0 \le \rho \le \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 \[lem:bound-marked\] in Section \[sec:errors\]): w.h.p. over the choice of $\Phi$, for every connected set of clauses $Z \subseteq \mathcal{C}$ we have $$\label{eq:num-marked:intro}
     \text{if } \ 2k^4 \log(n) \le \lvert Z \rvert \le b \log(n), \ \text{ then } \  \lvert \var(Z) \cap V \rvert \ge (r_0 - \delta) k \lvert Z \rvert.$$ The proof of Lemma \[lem:bound-marked\] 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 \[lem:tree-excess\]). 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$, @galanis2019counting [Lemma 40] shows that, as long as $L \ge \log n$, $$\label{eq:number-Y:intro}
     \text{for any clause }c\in\mathcal{C} \text{ we have } \left| \mathcal{Z}(c, L)\right| \le (9 k^2 \alpha)^L.$$ Once we have established and , 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 \le L \le 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-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}$, see Definition \[def:marginal\]. 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 \[def:subformula\]). 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 $$\label{eq:E1:intro}
     \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{E}_1(Z, S) \right) 
      \le  \frac{2^{-\delta k L}}{\lvert \mathcal{C} \rvert \cdot \lvert \mathcal{Z}(c, L) \rvert },$$ so the result would follow from a union bound over $c$ and $Z$. Let us give some insight on how we prove . 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-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}$, for each variable $v$ in $\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 $\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 \[sec:errors\] for details). Since the distribution $\mu$ is $(1/k)$-uniform, each one of these factors can be bounded by $\exp(1/k)/2$, obtaining $$\label{eq:E1:step}
     \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left(  \mathcal{E}_1(Z, S)\right)  
      \le  \left( \frac{1}{2} \exp\big(\frac{1}{k}\big) \right)^{\lvert \var(Z) \cap (V \setminus S) \rvert}.$$ In we gave a lower bound on $\lvert \var(Z) \cap V \rvert$, which can be applied in conjunction with to conclude, after some calculations, that the bound given in holds.

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

Once we have established Lemmas \[lem:expectation\] and Lemma \[lem:cc-general\], we can derive the spectral independence bound given in Lemma \[lem:si\] without much difficulty. Moreover, we can use Lemma \[lem:cc-general\] to implement the $\rho$-uniform-block Glauber dynamics on the marked variables for $0 < \rho \le \lvert \mathcal{V}_m \rvert$ and complete our sampling algorithm, which we explicitly state in Section \[sec:po:alg\].

The sampling algorithm {#sec:po:alg}
----------------------

To complete this proof outline, we explicitly describe Algorithm \[alg:main\], 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-\nulldelimiterspace   \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 \[sec:sample\]. Lemma \[lem:sample\] is our main result on $\operatorname{Sample}(\Phi^\Lambda, S)$.

\[lem:sample\] <span> There is an integer $k_0 \ge 3$ such that, for any integers $k \ge k_0$, $\xi \ge 1$ and any density $\density \le \densitymaindef$, the following holds w.h.p. over the choice of $\Phi = \Phi(k, n, \lfloor \density 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-\nulldelimiterspace   \mu_{\Omega^{\Lambda}}     \right|_{S}   }}$ in time $O( \lvert S \rvert \log n )$.</span>

The method $\operatorname{Sample}(\Phi^\Lambda, S)$ is used in Algorithm \[alg:main\] 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 \[lem:cc-general\]. We can now introduce Algorithm \[alg:main\].

\[H\]

\[1\]

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 \[prop:bad\].

Let $\varepsilon = n^{-\xi}$. Compute a marking $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$ for $\Phi$ as in Lemma \[lem:marking\] 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}_m$, sample $X_0(v) \in \{\mathsf{F}, \mathsf{T}\}$ jessicabrown@example.net.

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

Let $\Lambda_t$ be the assignment $X_{t-1}$ restricted to $\mathcal{V}_m \setminus S$.

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

$X_t \leftarrow \Lambda_t \cup Y$.

$Y \leftarrow \operatorname{Sample}(\Phi^{X_T}, \mathcal{V}_a \cup \mathcal{V}_c)$.

$X_T \cup Y$.

We remark here that Algorithm \[alg:main\] 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 \[lem:mixing-time\].

Paper outline
=============

The rest of this work is organised as follows. In Section \[sec:bad\] we introduce the procedure for determining bad clauses. In Section \[sec:marking\] we prove Proposition \[prop:marginals\] on markings of random formulas. In Section \[sec:errors\] we prove our technical result on the connected components of $\Phi^\Lambda$, Lemma \[lem:cc-general\]. In Section \[sec:sample\] we give the method $\operatorname{Sample}$ and prove Lemma \[lem:sample\]. In Section \[sec:mixing-time\] we prove the results on spectral independence stated in Section \[sec:po:si\] of the proof outline. Finally, in Section \[sec:alg\] we complete the proof of Theorem \[thm:sampling\] by combining our mixing time results (Lemma \[lem:mixing-time\]), our algorithm to sample from small connected components (Lemma \[lem:sample\]) and our result on the size of the connected components of $\Phi^{\Lambda}$ (Lemma \[lem:cc-general\]).

To help keep track of the notation and definitions introduced in this work, the reader is referred to the tables in Appendix \[ap:notation\]. We have also attached a table with all the results proved in this work and links to their proofs in Appendix \[ap:results\].

High-degree and bad variables in random CNF formulas {#sec:bad}
====================================================

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 \[def:degree\]. 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 \[alg:bad\]. Here $\bv$ denotes the set of bad variables and $\bc$ denotes the set of bad clauses.

\[H\]

\[1\]

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$

$i \leftarrow i + 1$

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

$\mathcal{C}_i \leftarrow \{c \in \mathcal{C} : \lvert \var(c) \cap \mathcal{V}_i \rvert \ge 3 \}$

$\bc \leftarrow \mathcal{C}_i$ and $\bv \leftarrow \mathcal{V}_i$

$\bv, \bc$

We define the *good clauses* of $\Phi$ as $\gc = \mathcal{C} \setminus \bc$ and the *good variables* of $\Phi$ as $\gv = \mathcal{C} \setminus \bv$. We will use the observations given in Proposition \[prop:bad\] several times in this work.

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

\[prop:bad:proof\] In this proof we briefly explain the implementation of Algorithm \[alg:bad\] announced in the statement. First, for each clause $c$ we keep track of the number of bad variables in $\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')$ by $1$ for those clauses $c'$ where $v$ appears. If any of these updates gives $\operatorname{bad}(c') \ge 3$, we add $\var(c')$ to the stack $S_{\mathcal{V}}$, set the variables in $\var(c')$ as bad and set the clause $c'$ 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 $m k$ times (once per literal in $\Phi$), the running time is $O(n + m k)$.

In our work we need a variation of a result of @galanis2019counting that controls the number of bad clauses in connected subgraphs of $G_\Phi$. We state this result in Lemma \[lem:bad\] and prove it in Appendix \[sec:ap:bad\].

\[<span>Modified version of @galanis2019counting [Lemma 8.16]</span>\] \[lem:bad\] <span>There is an integer $k_0 \ge 3$ such that for any integer $k \ge k_0$ and any density $\density \le \alpha_0 = \densitydef$, the following holds w.h.p. over the choice of the random $k$-CNF formula $\Phi = \Phi(k, n, \lfloor \density n\rfloor)$. For every connected set of clauses $Y$ in $G_\Phi$ such that $\lvert \var(Y) \rvert \ge  2k^4  \log n$, we have $\lvert Y \cap \bc \rvert \le  \lvert Y \rvert / k$.</span>

Lemma \[lem:bad\] 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 $\gv, \bv, \gc$ and $\bc$ given in @galanis2019counting use the condition $\lvert \var(c) \cap \mathcal{V}_i \rvert \ge k/10$ instead of $\lvert \var(c) \cap \mathcal{V}_i \rvert \ge 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 \[lem:bad\] given in @galanis2019counting can be extended to our setting. These changes are explained in Appendix \[sec:ap:bad\].

Identifying a set of "marked" variables with good marginals {#sec:marking}
===========================================================

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 @moitra19, 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 \[def:distributed-marking\] 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 @erdos1975. 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 \[lem:linearity\]). 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 \[lem:linearity\] to avoid these restrictions.

\[lem:linearity\] For any $k \ge 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 \var(c) \rvert \ge k - 1$ and $\lvert \var(c) \cap \var(c')\rvert \le 2$ for all $c, c' \in \mathcal{C}$ with $c \ne c'$.

\[lem:linearity:proof\] First, let us prove that, for $k \ge 3$, w.h.p. over the choice of $\Phi$, $\lvert \var(c) \rvert \ge 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 \var(c) \rvert \le k-2$. We claim that $\pr(\mathcal{R}_c) \le 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 $\pr(\mathcal{R}_c) \le q(k) / n^2$, and $\pr(\bigcup_{c \in \mathcal{C}}\mathcal{R}_c) \le q(k) m / n^2 \le  q(k) \density /n = O(1/n)$, so the result follows.

Let $c, c' \in \mathcal{C}$ with $c \ne c'$. We study $\lvert \var(c) \cap \var(c') \rvert$, $$\pr \left( \left| \var(c) \cap \var(c') \right| \ge 3 \right) \le \frac{n (n-1) (n-2) n^{2(k-3)} (k(k-1)(k-2))^2 }{n^{2k}} \le \frac{k^6}{n^3}.$$ Therefore, the probability that there is a pair of clauses $c, c'$ with $\lvert \var(c) \cap \var(c') \rvert \ge 3$ is bounded from above by $\frac{m(m-1)}{2} \frac{k^6}{n^3} \le  \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 @Spencer1997. 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 \ne B$ and $A$ and $B$ are not independent. In this setting, $\pr_P(B)$ is the probability that the event $B$ holds when sampling all the random variables in $\mathcal{P}$.

\[<span>Asymmetric Lovász local lemma, @Haeupler2011 [Theorems 1.1 and 2.1]</span>\] \[thm:lll\] 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 $$\pr_P\left(A\right) \le x(A) \prod_{N \in \Gamma(A) } \left(1 - x(N) \right),$$ then $\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 $$\pr_P\left( B \left| \, \bigcap\nolimits_{A \in \mathcal{A}} \overline{A} \right. \right) \le \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 \[lem:marking\] to find an $r_0$-marking of $\Phi$ (Definition \[def:distributed-marking\]), w.h.p. over the choice of the random formula, for some appropriate $r_0 \in (0, 1)$. Before proving Lemma \[lem:marking\], 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 \[def:distributed-marking\]) 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 \[lem:bound-marked\] 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 \[lem:marginals\]). We remark that, in the definition of $r$-distributed set of variables, we ask for $\lvert \var(c) \cap V \rvert \ge r (k-3)$ instead of $\lvert \var(c) \cap V \rvert \ge r k$ to account for the fact that w.h.p. a good clause has at most a repeated variable (Lemma \[lem:linearity\]) and at most two bad variables (Proposition \[prop:bad\]), which will come up in the proofs presented in this section. First, we need the following definition.

\[ $\Phi_{\mathrm{good}}$, $\Phi_{\mathrm{bad}}$\] \[def:good-phi\] Let $\Phi = (\mathcal{V}, \mathcal{C})$ be a $k$-CNF formula. Let $\Phi_{\mathrm{good}} = (\gv, \gc)$ 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 $\gc$ are adjacent if and only if $\var(c_1) \cap \var(c_2) \cap \gv \ne \emptyset$. By definition of good variables, the maximum degree in $G_{{\Phi_{\mathrm{good}}}}$ is at most $k (\mdeg - 1)$, which will be important when applying the LLL. We also need the following version of Chernoff's bounds.

\[<span>Chernoff's bounds - @mulzer2018 [Theorem 2.1 and Corollary 4.1]</span>\] \[lem:chernoff\] 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 $\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 $\pr \left( X \ge r n  \right) \le e^{-D(r, p) n}$ and $\pr \left( X \le s n  \right) \le 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 \[lem:marking\] are standard in the literature since the work of Moitra @moitra19 but the quantities involved are adapted to our setting.

\[lem:marking\] There is a positive integer $k_0$ such that for any $k \ge k_0$ and any density $\alpha$ with $\density \le \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.  \[item:marking:1\] there exists a partial assignment of bad variables that satisfies all bad clauses;

2.  \[item:marking: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 \[lem:marking\]\] \[lem:marking:proof\] We note that for any $k \ge 4$ our density $\density \le \alpha_0 = \densitydef$ is below the threshold $c_k > 1.3836 \cdot 2^k /k$ established in @alan1996 [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 \[prop:bad\]) and, thus, the restriction of a satisfying assignment to $\bv$ must satisfy all the bad clauses. In the rest of this proof we show that assertion \[item:marking:2\] also holds.

In view of Lemma \[lem:linearity\], we may assume that $\lvert \var(c) \rvert \ge k -1$ for all $c \in \mathcal{C}$. Let us find the $r_0$-marking $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$. If all clauses are bad, then we set $\mathcal{V}_c = \mathcal{V}$, $\mathcal{V}_m = \emptyset$ and $\mathcal{V}_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 $1/3$, "auxiliary" with probability $1/3$ and "control" with probability $1/3$. 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 \gv\}$, where $P_v$ is the random choice made in this experiment for $v$. Let $\mathcal{V}_m$ be the set of marked variables, let $\mathcal{V}_a$ be the set of auxiliary variables, and let $\mathcal{V}_c$ be the set of control variables obtained by running this experiment. For each clause $c \in \gc$, 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 $r_0 (k-3)$ good control variables. We are going to apply the LLL on the formula $\Phi_{\mathrm{good}}$ so as to show that $\pr( \bigcap\nolimits_{c \in \gc} \overline{A_c}) > 0$. For each $c \in \gc$, in view of Proposition \[prop:bad\] and the fact that $\lvert \var(c) \rvert \ge k-1$, we have $\lvert \var(c) \cap \gv \rvert \ge k-3$. Hence, we can apply the Chernoff bound given in Lemma \[lem:chernoff\] with $n = \lvert \var(c) \cap \gv\rvert$, $p = 1/3$ and $s = r_0$ to obtain, for any choice $V \in \{\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_{c} \setminus \bv\}$, $$\pr_{P} \left( \lvert  \var(c) \cap V \rvert < r_0 (k-3) \right) \le e^{-D(r_0, 1/3) (k-3)}.$$ We have chosen $r_0$ to be as large as possible under the restriction that $D(r_0, 1/3) \ge r_0 \log 2$. We conclude that $$\pr_{P} \left( A_c \right) \le 3 \cdot e^{-D(r_0, \beta) (k-3)}\le 3 \cdot 2^{-r_0 (k-3)}.$$ Let $\Delta_0 = 2^{r_0(k-3)}/(3 e^2 k)$ and let $x(A_c) = 1 / (k \Delta_0)$ for all $c \in \gc$. We check that $x$ satisfies the condition of the LLL for $\mathcal{P}$ and $\mathcal{A} = \{A_c : c \in \gc\}$. For $k \ge 80$, we find that $\Delta_0 > 1$ so $x(A_c) \in (0,1)$ for all $c \in \gc$. We note that $\Gamma(A_c) = \{A_{c'} : c' \in \gc, c' \ne c, \var(c') \cap \var(c) \cap \gv \ne \emptyset\}$. The graph $G_{\Phi_{\mathrm{good}}}$, given in Definition \[def:graph-phi\], has maximum degree at most $k(\mdeg - 1)$, so $\lvert \Gamma(A_c)\rvert \le k(\mdeg - 1) \le k \Delta_0$, where the latter inequality holds for large enough $k$ as $\Delta = \mdegdef$ (recall that $\delta = \deltadef$). Therefore, we have $$\label{eq:xc}
     x(A_c) \prod_{N \in \Gamma(A_c)} \left( 1 - x(N) \right) \ge  \frac{1}{k \Delta_0} \left( 1 - \frac{1}{k \Delta_0} \right)^{k \Delta_0} \ge \frac{1}{e^2 k \Delta_0} = 3 \cdot 2^{-r_0 (k-3)},$$ where we used $(1-1/z)^{z} \ge e^{-2}$ for all $z \ge 2$ in the second inequality. Thus, $$x(A_c) \prod_{N \in \Gamma(A_c)} \left( 1 - x(N) \right) \ge 
   3 \cdot 2^{-r_0 (k-3)} \geq   \pr_{P} \left( A_c \right).$$ We conclude that, by the LLL, $\pr_{P}\left(\, \bigcap\nolimits_{c \in \gc} \overline{A_c} \, \right) > 0$, so there exists a partition $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$ of the variables of $\Phi$ such that $\bv \subseteq \mathcal{V}_c$ and each good clause contains at least $r_0 (k-3)$ variables of each one of the sets $\mathcal{V}_m, \mathcal{V}_a$ and $\mathcal{V}_{c} \setminus \bv$. That is, $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$ satisfies items \[item:def-marking:1\] and \[item:def-marking:2\] of Definition \[def:distributed-marking\] for $r = r_0$. Moreover, with probability at least $1-\delta$, this partition can be computed in $4 n \alpha \Delta_0 k \log(1/\delta)$ steps with the algorithm of Moser and Tardos @moser2010.

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 \[def:subformula\]) on any marked and auxiliary variable. In fact, we prove the stronger result that the marginal distribution of $\mu_{\Omega}$ on $\mathcal{V}_m \cup \mathcal{V}_a $ is very close to the uniform distribution. Recall also that all the variables in bad clauses of $\Phi$ are bad (Proposition \[prop:bad\]), and thus, we can consider the subformula $\Phi_{\mathrm{bad}} := (\bv, \bc)$, which is satisfiable under the hypothesis of Lemma \[lem:marking\].

\[lem:marginals\] Let $\Phi = (\mathcal{V}, \mathcal{C})$ be a $k$-CNF formula that has an $r_0$-marking $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$. Then either the formula $\Phi_{\mathrm{bad}}$ is unsatisfiable or the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m \cup \mathcal{V}_a}   }}$ is $(2^{-\delta k}/k)$-uniform.

\[lem:marginals:proof\] Let us assume that $\Phi_{\mathrm{bad}}$ is satisfiable and let us prove that the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m \cup \mathcal{V}_a}   }}$ (Definition \[def:marginal\]) 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}_m \cup \mathcal{V}_a$ and let $\Lambda$ be an assignment of $\mathcal{V}_m \cup \mathcal{V}_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 $\pr_{\mu_{\Omega^{\tau}}}\left( \cdot \right) =  \pr_{\mu_{\Omega}}\left( \cdot \, \vert \tau \right)$ for any assignment $\tau$ of some variables. In light of this observation, we are going to prove that $$\label{eq:proof-marginals}
         \max \left\{ \pr_{\mu_{\Omega^{\Lambda \cup \Lambda_{bad}}}}\left(v \mapsto \mathsf{F}\right), \pr_{\mu_{\Omega^{\Lambda \cup \Lambda_{bad}}}}\left(v \mapsto \mathsf{T}\right)  \right\}  \le  \frac{1}{2} \exp \left( \frac{1}{k 2^{\delta k}} \right).$$ 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' := \Phi^{\Lambda \cup \Lambda_{bad}}$ as follows. Let $\mathcal{V}'$ and $\mathcal{C}'$ be the sets of variables and clauses of $\Phi'$. Note that, $\mathcal{V}' \subseteq \gv$, $\mathcal{C}' \subseteq \gc$ and $G_{\Phi'}$ 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}'$, where $\sigma \colon \mathcal{V}' \to \{\mathsf{F}, \mathsf{T}\}$ is chosen uniformly at random from the set of assignments $\mathcal{V}' \to \{\mathsf{F}, \mathsf{T}\}$, and $\mathcal{P} = \{P_v : v \in \mathcal{V}'\}$. We define the set $\mathcal{A}$ as the set containing for all $c \in \mathcal{C}'$ the event $A_c = $ "the clause $c$ is not satisfied by the random assignment $\sigma$". By the definition of $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$, there are at least $\rh (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}'$, we have $\pr_{P}(A_c) \le 2^{-\rh (k-3)}$. Recall that $\Delta = \mdegdef$ (Definition \[def:degree\]). Let $\Delta_0 = 2^{r_0(k-3)}/(3 e^2 k)$ and let $x(A_c) = \frac{1}{k \mdeg_0}$ for all $c \in \mathcal{C}'$, following the same idea as in . Let us show that $x$ satisfies the LLL condition in this setting. In view of $\Gamma(A_c) = \{A_{c'} : c' \in \mathcal{C}' :  c' \neq c, \var(c) \cap \var(c') \cap \mathcal{V}' \ne \emptyset\}$, which can be identified with a subset of the neighbours of $c$ in $G_{\Phi_{\mathrm{good}}}$, and , we find that $$x(A_c) \prod_{N \in \Gamma(A_c)} \left( 1 - x(N) \right) \ge  3 \cdot 2^{-r_0 (k-3)} \ge \pr_{P} \left( A_c \right).$$ Let $A = \{v \mapsto \mathsf{T}\} :=  
   \{\sigma\colon \mathcal{V}' \to \{\mathsf{F}, \mathsf{T}\} \text{ with } \sigma(v) = \mathsf{T}\}$. In $\Phi'$, we have $\Gamma(A) = \{A_c : c  \in \mathcal{C}', v \in \var(c) \}$, so $\lvert \Gamma(A) \rvert < \mdeg$. By the LLL, we obtain $$\pr_P\left( v \mapsto \mathsf{T} \left| \, \bigcap\nolimits_{c \in \mathcal{C}'} \overline{A_c} \right. \right) \le \frac{1}{2} \prod_{N \in \Gamma(A) } \big(1 - x(N) \big)^{-1} \le \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)\le \exp(1/(x-1))$. We find that $$\pr_P\left( v \mapsto \mathsf{T} \left| \, \bigcap\nolimits_{c \in \mathcal{C}'} \overline{A_c} \right. \right) \le \frac{1}{2} \exp \left(\frac{\Delta - 1}{k \Delta_0 - 1}\right) \le \frac{1}{2} \exp \left(\frac{1}{k 2^{\delta k}}\right),$$ where in the latter inequality we used $(p-j)/(q-j) \le p/q$ for all $0 < j < p \le q$ and the fact that $\Delta = \mdegdef \le 2^{- \delta k} \cdot 2^{r_0(k-3)}/(3 e^2 k) = 2^{- \delta k} \Delta_0$ for large enough $k$. We note that $\pr_{\mu_{\Omega^{\Lambda \cup \Lambda_{bad}}}}\left( \cdot \right) =  \pr_{P}\left( \cdot \, \vert \bigcap\nolimits_{c \in \mathcal{C}'} \overline{A_c}\, \right)$, which completes the proof of one of the upper bounds of . The other upper bound is proved analogously by applying the LLL with $A = \{v \mapsto \mathsf{F}\}$.

The $(2^{-\delta k}/k)$-uniform property proved in Lemma \[lem:marginals\] 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 \[lem:marginals\] to the distributions computed by the Glauber dynamics on the marked variables.

\[cor:marginals:glauber\] 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}_m, \mathcal{V}_a, \mathcal{V}_c)$. Let $\rho$ be an integer with $1 \le \rho < \lvert \mathcal{V}_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 jessicabrown@example.net. Then the probability distribution of $X_t$ is $(2^{-\delta k}/k)$-uniform.

\[cor:marginals:glauber:proof\] Let $\epsilon = (2^{-\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 $\epsilon$-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}_m$, the claim holds for $t = 0$. Let us now assume that $\pi_{t-1}$ is $\epsilon$-uniform and let us prove that this is also the case for $\pi_t$. To show the desired uniformity of $\pi_t$ (cf. Definition \[def:uniform\]), consider arbitrary $v \in \mathcal{V}_m$ and $\Lambda \colon \mathcal{V}_m \setminus \{v\} \to \{\mathsf{F}, \mathsf{T}\}$, we need to bound $\pr_{\pi_t}\left( \left. v \mapsto \mathsf{F} \right|  \Lambda \right)$ and $\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}_m \setminus V_t$. Thus, we have $\pr_{\pi_t}\left( \left. v \mapsto \mathsf{F} \right| \Lambda \right) = \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-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m \cup \mathcal{V}_a}   }}$ is $\epsilon$-uniform by Lemma \[lem:marginals\], we conclude that $\pr_{\pi_t}\left( \left. v \mapsto \mathsf{F} \right| \Lambda \right) = \pr_{\mu_{\Omega^{\Lambda}}}\left(v \mapsto \mathsf{F} \right) \le \frac{1}{2}\exp(\epsilon)$. 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 $\pr_{\pi_t}\left( \left. v \mapsto \mathsf{F} \right| \Lambda \right) = \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}_m \setminus \bigcup_{i \in \{j+1, j+2, \ldots, t\}} V_i$. By the induction hypothesis, $\pr_{\pi_t}\left( \left. v \mapsto \mathsf{F} \right| \Lambda \right) = \pr_{\pi_j}\left( \left. v \mapsto \mathsf{F}  \right| \Lambda_j \right) \le (1/2) \exp(\epsilon)$. 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}_m, \mathcal{V}_c)$. Here auxiliary variables play an essential role in bounding the influences between marked variables as we illustrated in Section \[sec:po\]. 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}_m$.

\[cor:size-r-distributed\] There is an integer $k_0$ such that for any $k \ge k_0$ and any density $\alpha$ with $\density \le \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 \ge (r_0 - \delta) (k \alpha / \Delta) n$.

\[cor:size-r-distributed:proof\] W.h.p. over the choice of $\Phi$, Lemma \[lem:bad\] holds. We combine this with the inequality $\alpha_0 \le \Delta / k^3$ and the fact that a good variable occurs in at most $\Delta$ good clauses to find that $$\lvert V \rvert \ge \frac{r_0 (k-3) \lvert \gc \rvert}{\Delta} \ge \frac{r_0 (k-3)}{\Delta} \left(1-\frac{1}{k}\right) \lvert \mathcal{C} \rvert  \ge \frac{r_0 (k-4)}{\Delta} (\alpha n -1),$$ which is at least $(r_0 - \delta) (k \alpha / \Delta) n$ for large enough $k$.

Analysis of the connected components of $\Phi^{\Lambda}$ {#sec:errors}
========================================================

In this section we prove Lemma \[lem:cc-general\], 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 \[sec:errors:log\] is devoted to this purpose. In Section \[sec:errors:nmarked\] we apply the results of Section \[sec:errors:log\] to obtain a lower bound of the number of marked/auxiliary variables in logarithmic-sized sets of clauses. Finally, in Section \[sec:errors:proof\] we complete the proof of Lemma \[lem:cc-general\].

Logarithmic-sized sets of clauses in the random k-SAT model {#sec:errors:log}
-----------------------------------------------------------

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 \[lem:tree-excess\] and is essential to our proofs.

\[lem:tree-excess\] Let $k \ge 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,  2 b \log(e k^2 \alpha) \}$.

\[lem:tree-excess:proof\] Let $n$ be the number of variables and $m$ be the number of clauses of $\Phi$, so $m/n \le \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 $$\label{eq:tree-excess}
   \binom{m}{\ell} \ell^{\ell-2} \binom{\ell (\ell-1) / 2}{c+1} \left( \frac{k^2}{n} \right)^{\ell+c},$$ 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  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} \le (e p / q)^q$ and $m/n \le \alpha$ we can bound  by $$\label{eq:tree-excess:2}
  \begin{aligned}
   \left( \frac{e m}{\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} & \le \left( \frac{e m}{\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} \\
   & = \left(\frac{e}{2c+2}\right)^{c+1} \left( \frac{e m k^2 }{n} \right)^\ell  \left( \frac{k^2 \ell^2}{n} \right)^{c} \\ 
  & \le \left(\frac{e}{2c+2}\right)^{c+1} \left(e k^2 \alpha \right)^\ell  \left( \frac{k^2 \ell^2}{n} \right)^{c}.
  \end{aligned}$$ Now we distinguish two cases:

-   Case when $e k^2 \alpha \le 1$ . We have $c = 1$ by definition. Thus,  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 $e k^2 \alpha > 1$. Then, as $\ell \le b \log n$ and $b \log(e k^2 \alpha) \le c/2$ by definition, we have $$\left( e k^2 \alpha \right)^\ell \le \left( e  k^2 \alpha \right)^{b \log n}  = n^{b \log(e k^2 \alpha)} \le n^{c/2}.$$ We conclude that  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 \[lem:bad\] we established that, in sets of clauses that have at least $2 k^4 \log n$ variables, the number of bad clauses of $\Phi$ is not too large. We aim to apply Lemma \[lem:bad\] to logarithmic-sized sets of clauses. In general, $\lvert Y \rvert$ might be significantly larger than $\lvert \var(Y) \rvert$, so it is not clear how to apply Lemma \[lem:bad\]. However, in the random $k$-CNF formula setting the following holds.

\[lem:bound-Y\] Let $k \ge 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 \ge a \log n$, we have $\lvert \var(Y) \rvert \ge a \log n$.

\[lem:bound-Y: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 \var(Y) \rvert \le \ell$, we have $\lvert Y \rvert \le \ell$. We note that if there is a set of clauses $Y$ with $\lvert \var(Y) \rvert \le \ell$ and $\lvert Y \rvert > \ell$, then for any subset $Y'$ of $Y$ with $\lvert Y' \rvert = \ell +1$ we have $\lvert \var(Y') \rvert \le \lvert \var(Y) \rvert \le  \ell$. Hence, it suffices to prove that there is no set $Y$ of clauses with $|\var(Y)| \leq \ell$ and $|Y|=\ell+1$. We can assume $n$ is large enough so that $\ell \le 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 $$\begin{aligned}
    \pr \left( \mathcal{E} \right) \le \binom{m}{\ell+1} \binom{n}{\ell} \left(\frac{\ell }{n} \right)^{(\ell+1) k},
  \end{aligned}$$ 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} \le (e p / q)^{q}$, we obtain $$\begin{aligned}
    \pr \left( \mathcal{E} \right) & \le \left(\frac{e m}{\ell+1}\right)^{\ell+1}  \left(\frac{e n}{\ell}\right)^{\ell} \left(\frac{\ell }{n} \right)^{(\ell+1) k} \le \left(\frac{e m}{\ell}\right)^{\ell+1}  \left(\frac{e n}{\ell}\right)^{\ell+1} \left(\frac{\ell }{n} \right)^{(\ell+1) k} \\
    & \le \left(\frac{e \alpha n}{\ell}\right)^{\ell+1}  \left(\frac{e n}{\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},
  \end{aligned}$$ which is $O(\log(n) / n)$ because $k \ge 3$ and $\ell = O (\log n)$.

Number of marked variables in logarithmic-sized sets of clauses {#sec:errors:nmarked}
---------------------------------------------------------------

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 = \densitydef$ (Definition \[def:degree\]).

\[lem:bound-marked\] Let $\hat\delta \in (0, r_0)$. There is a positive integer $k_0$ such that, for any integer $k \ge k_0$, any density $\alpha \le \alpha_0$ and any real number $b$ with $2 k^4  < b$, the following holds w.h.p. over the choice of $\Phi = \Phi(k, n, \lfloor \density 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) \le \lvert Y \rvert \le b \log (n)$, we have $\lvert \var(Y) \cap V \rvert \ge (r_0 - \hat\delta) k \lvert Y \rvert$.

\[lem:bound-marked:proof\] Let $a=2 k^4$. We apply Lemma \[lem:bad\] to find that there is $k_1$ such that for $k \ge k_1$, w.h.p. over the choice of $\Phi$, for every set of clauses $Y$ that is connected in $G_{\Phi}$, $$\label{eq:cbad}
     \text{if } \ \lvert \var(Y) \rvert \ge a \log(n), \text{ then }  \lvert Y \cap \bc \rvert \le \lvert Y \rvert / k.$$ We apply Lemma \[lem:bound-Y\] with $a = 2k^4$ to find that, w.h.p. over the choice of $\Phi$, for every set of clauses $Y$, we have $$\label{eq:Y-bound}
  \begin{aligned}
     \text{if } & \ \lvert Y \rvert \ge a \log(n), \text{then } \lvert \var(Y)  \rvert \ge a \log(n).
  \end{aligned}$$ Finally, for any $b>0$, we apply Lemma \[lem:tree-excess\], obtaining that, w.h.p. over the choice of $\Phi$, for every set of clauses $Y$ that is connected in $G_{\Phi}$, $$\label{eq:errors:tree-excess}
      \text{if } \lvert Y \vert \le b \log n, \text{ then }  Y \text{ has tree-excess at most } c= \max \{1, 2 b \log (e  k^2 \alpha)\} = O(1).$$

Let $Y$ be a set of clauses that is connected in $G_{\Phi}$ such that $a \log(n) \le \lvert Y \rvert \le b \log (n)$. Then, by  and , we have $\lvert Y \cap \gc \rvert \ge \lvert Y \rvert (1 - 1 / k)$. By definition of $r_0$-distributed (Definition \[def:distributed-marking\]), 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 , and two distinct clauses only share at most two variables by Lemma \[lem:linearity\], we have $$\begin{aligned}
     \lvert \var(Y) \cap V \rvert & \ge r_0(k - 3) \left(1 - \frac{1}{k}\right) \lvert Y \rvert - 2 (\lvert Y \rvert + c - 1) \\
      & \ge (r_0 (k - 4) - 2) \lvert Y \rvert - 2(c-1).
    \end{aligned}$$ There is $k_0 \ge k_1$ such that for $k \ge k_0$, we find that, for any set of clauses $Y$ that is connected in $G_{\Phi}$ and has $a \log(n) \le \lvert Y \rvert \le b \log (n)$, $\lvert \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 \var(Y) \cap V \rvert \ge  (r_0 - \hat\delta) k \lvert Y \rvert$ and the result follows.

Proof of Lemma \[lem:cc-general\] {#sec:errors:proof}
---------------------------------

There is an integer $k_0 \ge 3$ such that, for any integer $k \ge k_0$, any density $\density \le \densitymaindef$, 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 \density n\rfloor)$.

Let $L$ be an integer satisfying $a \log n \le L \le 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 \le \rho \le \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-\nulldelimiterspace   \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 \ge  L$ such that all clauses in $Y$ are unsatisfied by $\Lambda$. Then $
    \pr_{S \sim \tau} \left( \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{F} \right) \le 2^{- \delta k L}  \right) \ge 1 - 2^{-\delta k L}$.

\[lem:cc-general:proof\] Since $\delta = 0.00001$, $a = 2k^4$, $r = \rmain$, and $r_0 = \rvalue$, we can pick $k_0$ large enough so that for all $k \ge k_0$ we have $$\label{eq:cc-alpha}
     2^{rk} \le \frac{2^{(r_0 - 3 \delta)k}}{18 e k^3} \le \alpha_0 = \densitydef.$$ We apply Lemma \[lem:bound-marked\] 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 $$\label{eq:num-marked}
     \text{if } \ a \log(n) \le \lvert Z \rvert \le b \log(n), \ \text{ then } \  \lvert \var(Z) \cap V \rvert \ge (r_0 - \delta) k \lvert Z \rvert.$$ 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$, @galanis2019counting [Lemma 40] shows that, as long as $L \ge \log n$, $$\label{eq:number-Y}
     \text{for any clause }c\in\mathcal{C} \text{ we have } \left| \mathcal{Z}(c, L)\right| \le (9 k^2 \alpha)^L.$$ The facts that we have just established using Lemma \[lem:bound-marked\] and @galanis2019counting [Lemma 40] are all the properties of random formulas that we need in this proof.

Let $L$ be an integer with $a \log n \le L \le 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-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}$, see Definition \[def:marginal\]. Recall that $Z \subseteq \mathcal{C}^{\Lambda}$ means that none of the clauses in $Z$ are satisfied by the assignment $\Lambda$ (Definition \[def:subformula\]). 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$, $$\label{eq:claim-cc}
   \pr_{S \sim \tau} \left( \ \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \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 k L} \   \right) \le 2^{- \delta k L},$$ which is equivalent to the result stated in this lemma. We note that the left-hand side of  can be upper bounded by $$\label{eq:claim-cc-sum}
 \begin{aligned}
   & \pr_{S \sim \tau} \left(  \exists c \in \mathcal{C}, Z \in \mathcal{Z}(c, L) :   \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{E}_1(Z, S) \right) > \frac{2^{- \delta k L}}{\lvert \mathcal{C} \rvert \cdot \lvert \mathcal{Z}(c, L) \rvert } \right) \le \\
   & \sum_{c \in \mathcal{C}, Z \in \mathcal{Z}(c, L)} \pr_{S \sim \tau} \left(    \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{E}_1(Z, S) \right) > \frac{2^{- \delta k L}}{\lvert \mathcal{C} \rvert \cdot \lvert \mathcal{Z}(c, L) \rvert }  \right).
   \end{aligned}$$ We are going to show that, for any $c \in \mathcal{C}$ and $Z \in \mathcal{Z}(c, L)$, $$\label{eq:individual-Z-bound}
    \pr_{S \sim \tau} \left(  \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{E}_1(Z, S) \right) > \frac{2^{- \delta k L}}{\lvert \mathcal{C} \rvert \cdot \lvert \mathcal{Z}(c, L) \rvert }  \right) \le \left( 2 e k \cdot  2^{-(r_0 - \delta) k} \right)^L.$$ Before proving , let us complete the proof assuming that this inequality holds. Recall that $\density \le \densitymaindef$ and that, in the first line of this proof, we chose $k_0$ large enough so that $2^{k r} \le 2^{(r_0 - 3\delta)k} / (18 e k^3 )$. Hence, in light of , we have $\lvert \mathcal{Z}(c, L) \rvert \le (2^{(r_0 - 3 \delta) k}/(2 e k))^L$. We use the following observation, $$\label{eq:bound-C}
  \text{for } k > 1/(\delta \log 2) \text{ and for large enough } n \text{, } \ \ \lvert \mathcal{C} \rvert \le n \alpha \le n^{\delta 2 k^5  \log 2} \le 2^{\delta k L}.$$ Combining ,  and , we conclude the left-hand size of  is bounded above by $$\sum_{c \in \mathcal{C}, Z \in \mathcal{Z}(c, L)} \left( 2 e k \cdot 2^{-(r_0-\delta) k } \right)^{L} 
   \le n \density \cdot \left(\frac{2^{(r_0 - 3 \delta) k }}{2 e k}\right)^L \cdot \left( 2 e k \cdot 2^{- (r_0-\delta) k } \right)^{L} 
   = n \density 2^{- 2\delta k L}  \le  2^{-\delta k L},$$ which completes the proof of , and hence the proof of the lemma, subject to .

To prove , we are going to find many $S$ for which $\pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} ( \mathcal{E}_1(Z, S) ) \le 2^{- \delta k L} / (\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$: $$\label{eq:E2:def}
\begin{aligned}
  \mathcal{E}_2(Z) := & `` \text{the random set } S \subseteq V \text{ that we select contains fewer} \\ 
  & \text{than }\ell := \lceil \lvert \var(Z) \cap V \rvert / k \rceil \text{ variables in } \var(Z) \cap V".
\end{aligned}$$ We will show (in equation ) 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 $\pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} ( \mathcal{E}_1(Z, S) ) \le 2^{- \delta k L} / (\lvert \mathcal{C} \rvert \cdot \lvert \mathcal{Z}(c, L) \rvert)$. If there are $c_1, c_2 \in Z$ and $v \in \var(c_1) \cap \var(c_2) \cap (V\setminus S)$ such that $c_1 \ne 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 $\pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} ( \mathcal{E}_1(Z, S) ) = 0$. Let us now consider the complementary case: $$\label{eq:complementary-case}
 \begin{aligned}
      &\text{for all $c_1, c_2 \in Z$ with $c_1 \ne c_2$ and $v \in \var(c_1) \cap \var(c_2) \cap (V\setminus S)$,} \\ 
      &\text{the literal of $v$ in $c_1$ is the same as the literal of $v$ in $c_2$.}
 \end{aligned}$$ 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 . Let $u_1, u_2, \ldots, u_t$ be the list of variables in $(\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-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}$. Then, by definition of $\mathcal{W}_j$, we have $$\begin{aligned}
     \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}}\left( \mathcal{E}_1(Z, S) \right)  
     & =  \prod_{j = 1}^t  \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}}\left( \mathcal{W}_j \left| \  \bigcap\nolimits_{i = 1}^{j-1} \mathcal{W}_i \right.\right).
 \end{aligned}$$ As $\mu$ is $(1/k)$-uniform, we find that $\pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}}( \mathcal{W}_j \vert \  \bigcap\nolimits_{i = 1}^{j-1} \mathcal{W}_i ) \le (1/2) \exp(1/k)$ for all $j \in \{1, 2, \ldots, t\}$. We conclude that $$\begin{aligned}
     \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left(  \mathcal{E}_1(Z, S)\right)  
     & \le  \left( \frac{1}{2} \exp\big(\frac{1}{k}\big) \right)^{t}.
  \end{aligned}$$ From  and the fact that $\mathcal{E}_2(Z)$ holds for $S$, we have $$t = \lvert \var(Z) \cap (V \setminus S) \rvert \ge \lvert \var(Z) \cap V \rvert - \lceil \lvert \var(Z) \cap V\rvert / k \rceil  \ge \lvert \var(Z) \cap V \rvert (1 - 1/k)  -1 \ge (r_0 - \delta) L (k-1) - 1.$$ It follows that $$\begin{aligned}
     \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{E}_1(Z, S) \right) 
     & \le \left(\frac{1}{2} \exp\Big(\frac{1}{k}\Big)\right)^{ (r_0 - \delta) (k-1) L-1}  \\
     & \le 2 \left( 2 \cdot 2^{-(r_0 - \delta) k } \exp\Big(\frac{ (r_0 - \delta)(k-1) }{k}\Big) \right)^{L} \\
     & \le \left( 4 e \cdot 2^{-(r_0 - \delta) k } \right)^{L},
 \end{aligned}$$ where we used that $1/2 \le (1/2) \exp(1/k) < 1$ in the second and third inequality. As $\alpha \le 2^{r k} \le 2^{(r_0 - 3 \delta) k} / (18 e k^3) \le 2^{(r_0 - 3 \delta) k} / (9 \cdot 4 e k^2)$ by hypothesis and , we find that $$\left( 4 e \cdot 2^{-(r_0 - \delta) k } \right)^{L} = \left(\frac{ 9 \cdot 4 e k^2 \cdot  \alpha \cdot 2^{-(r_0 -\delta) k }}{9 k^2 \alpha} \right)^{L}   \le  \left(\frac{ 2^{-2\delta k }}{9 k^2 \alpha} \right)^{L} \le  \frac{2^{-2 \delta k L}}{\lvert \mathcal{Z}(c, L) \rvert } \leq  \frac{2^{-\delta k L}}{ \lvert \mathcal{C} \rvert \cdot \mathcal{Z}(c, L) \rvert } ,$$ where in the second to last inequality we applied the bound on the size of $\mathcal{Z}(c, L)$ given in , and in the last inequality we used . As $S$ was picked as any subset of $V$ with $\lvert S \rvert = \rho$ such that $\mathcal{E}_2(Z)$ holds, it follows that $$\label{eq:cc-by-E2}
   \pr_{S \sim \tau} \left(  \pr_{\Lambda \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}} \left( \mathcal{E}_1(Z, S) \right) > \frac{2^{- \delta k L}}{\lvert \mathcal{C} \rvert \cdot \lvert \mathcal{Z}(c, L) \rvert } \right) \le  \pr_{S \sim \tau} \left( \overline{\mathcal{E}_2(Z)} \right).$$ In order to prove , which finishes the proof, we need to show $\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 , we obtain $\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 \var(Z) \cap V \rvert \ge \ell$ is at most $\binom{\lvert \var(Z) \cap V \rvert}{\ell}  \binom{\lvert V \rvert - \ell}{\rho -  \ell}$. Hence, we have $$\label{eq:prob-E2}
   \begin{aligned}
     \pr_{S \sim \tau} \left( \overline{\mathcal{E}_2(Z)} \right) & \le \binom{\lvert V \rvert }{\rho }^{-1}  \binom{\lvert \var(Z) \cap V \rvert}{\ell}  \binom{\lvert V \rvert  - \ell}{\rho  -  \ell} \\ 
     & = \frac{\rho (\rho -1) \cdots (\rho - \ell + 1)}{\lvert V \rvert  (\lvert V \rvert - 1) \cdots (\lvert V \rvert - \ell + 1)}   \binom{\lvert \var(Z) \cap V \rvert}{\ell} \\ 
     & \le \left(\frac{\rho}{\lvert V \rvert} \right)^{\ell} \left(\frac{e \lvert \var(Z) \cap V \rvert }{\ell} \right)^{\ell} \le \left(\frac{\rho}{\lvert V \rvert} e k \right)^{\ell},
    \end{aligned}$$ where we used $\ell := \lceil \lvert \var(Z) \cap V \rvert / k \rceil \ge \lvert \var(Z) \cap V \rvert / k$, $(p - i)/(q -  i)  \le p/q $ for any $0 < i < p < q$ and $\binom{p}{q} \le (e p / q)^q$. Combining this with the hypothesis $\rho \le \lvert V \rvert / 2^{k}$ and the bound $\ell \ge (r_0 - \delta) L$, see , we obtain $$\label{eq:E2}
     \pr_{S \sim \tau} \left( \overline{\mathcal{E}_2(Z)} \right) \le \left( e k 2^{-k} \right)^\ell \le \left( ( e k)^{r_0 - \delta} \cdot  2^{-(r_0 - \delta) k} \right)^L \le \left(2  e k \cdot  2^{-(r_0 - \delta) k} \right)^L.$$ The bound  follows from combining  and , which completes the proof.

Sampling from small connected components {#sec:sample}
========================================

In this section we prove Lemma \[lem:sample\]. Recall that Lemma \[lem:sample\] 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 \[lem:tree-excess\], and the fact that when $G_\Phi$ is acyclic, we can exactly count and sample satisfying assignments efficiently (Proposition \[prop:sample-trees\]).

\[prop:sample-trees\] 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)$.

\[prop:sample-trees: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'$ of $\Phi$, let $T_{c'}$ be the subtree of $T$ hanging from $c'$. For any assignment $\sigma \colon \var(c') \to \{\mathsf{F}, \mathsf{T}\}$, let $\operatorname{sa}(c', \sigma)$ denote the number of satisfying assignments of the formula determined by $T_{c'}$ that extend $\sigma$. Our goal is computing the number of satisfying assignments of $\Phi$, which, under this notation, is equal to $$\label{eq:tree}
     \operatorname{sa}(\Phi) := \sum_{\sigma \colon \var(c) \to \{\mathsf{F}, \mathsf{T}\}}\operatorname{sa}(c, \sigma).$$ We do this by computing $\operatorname{sa}(c', \sigma)$ for any clause $c'$ and any assignment $\sigma  \colon \var(c') \to \{\mathsf{F}, \mathsf{T}\}$. Using the tree structure of $T$, we show that $\operatorname{sa}(c', \sigma)$ satisfies a recurrence. There are two cases:

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

2.  $c'$ is not a leaf. Let $T_1, \ldots, T_l$ be the trees hanging from $c'$ 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', \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 $\var(c_j)$ that agree with $\sigma$ on $\var(c') \cap \var(c_j)$.

We can apply this recurrence with dynamic programming to compute $\operatorname{sa}(c, \sigma)$ for any assignment $\sigma \colon \var(c) \to \{\mathsf{F}, \mathsf{T}\}$. More explicitly, we compute $\operatorname{sa}(c', \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', \cdot)$ per clause $c'$ 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 . The overall procedure takes at most $O(4^k \lvert \mathcal{C} \rvert)$ steps since each entry $\operatorname{sa}(c', \sigma)$ is accessed at most $2^k$ times when computing the corresponding entries for the parent of $c'$, and there are at most $2^k \lvert \mathcal{C}(T) \rvert$ entries.

In Algorithm \[alg:counting\] we give an algorithm based on Proposition \[prop:sample-trees\] 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}}$.

\[H\]

\[1\]

a $k$-CNF formula $\Phi = (\mathcal{V},\mathcal{C})$ 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$.

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 \[prop:sample-trees\] 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)$.

$count$

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

\[prop:counting:proof\] We note that, in the execution of Algorithm \[alg:counting\], we have $\lvert \mathcal{V}_T \rvert \le k c$. Hence, there are at most $2^{k c}$ 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 \[prop:sample-trees\].

Even though the running time of Algorithm \[alg:counting\] 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 \[lem:tree-excess\], this is the case for logarithmic-sized subsets of clauses of random formulas. We can now finish the proof of Lemma \[lem:sample\].

<span> There is an integer $k_0 \ge 3$ such that, for any integers $k \ge k_0$, $\xi \ge 1$ and any density $\density \le \densitymaindef$, the following holds w.h.p. over the choice of $\Phi = \Phi(k, n, \lfloor \density 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-\nulldelimiterspace   \mu_{\Omega^{\Lambda}}     \right|_{S}   }}$ in time $O( \lvert S \rvert \log n )$.</span>

\[lem:sample:proof\] We apply Lemma \[lem:tree-excess\] 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, 2 b \log(e \density 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' = (\mathcal{V}', \mathcal{C}')$ be the subformula of $\Phi^{\Lambda}$ with $G_{\Phi'} = H$. The formula $\Phi'$ has size at most $b \log(n)$. Moreover, the graph $G_{\Phi'} = 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 \[prop:counting\] to count the number of satisfying assignments of $\Phi'^{v \to \mathsf{F}}$ and $\Phi'^{v \to \mathsf{T}}$ in time $O( 2^{k(c+2)} \lvert \mathcal{C}'\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-\nulldelimiterspace   \mu_{\Omega^\Lambda}     \right|_{S}   }}$. This assignment has been computed in $O(\lvert S \rvert \log n)$ steps as we wanted.

Mixing time of the Markov chain {#sec:mixing-time}
===============================

In this section we study the mixing time of the $\rho$-uniform-block Glauber dynamics on the marked variables and prove Lemma \[lem:mixing-time\]. As explained in Section \[sec:po:si\], 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 @Chen2021. 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 @bez2021. Here we show that that sums of influences are at most $\epsilon \log n$ for small $\epsilon$ (Lemma \[lem:si\]). 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 \[sec:po:si:pw\], 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 \[sec:mixing-time:si\] we prove Lemmas \[lem:expectation\] and \[lem:si\]. In Section \[sec:mixing-time:mt\] we prove Lemma \[lem:mixing-time\].

Previous work on the Glauber dynamics for bounded-degree $k$-SAT formulas {#sec:po:si:pw}
-------------------------------------------------------------------------

In this section we explain why known arguments for bounding the mixing time of 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 @jain2021sampling, 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 \le C \, 2^{0.1742 \cdot k}/ k^3$, where $C > 0$ is a constant that does not depend on $k$.[^4] 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 @pcbook for the definition of coupling. 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 @jain2021sampling, based on the work on monotone $k$-CNF formulas presented in @hermon2019, 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 structure. Extending this idea to the random $k$-SAT model presents two main issues. First of all, the number of paths of any given length may be too large due to the presence of high-degree variables. Moreover, these paths may mostly have bad clauses, which are always unsatisfied in both chains and, thus, the probability that they are unsatisfied is not small. Similar issues arise in other bounded-degree approaches, such as @feng2020, where the mixing time argument only succeeds when $\hat\Delta \le 2^{k/20} / (8k)$.

Spectral independence in the $k$-SAT model {#sec:mixing-time:si}
------------------------------------------

In this section we prove Lemmas \[lem:expectation\] and \[lem:si\]. Recall that 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.

<span> There is an integer $k_0 \ge 3$ such that for any integer $k \ge k_0$ and any density $\alpha$ with $\density \le 2^{rk}$ 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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$, the sum of influences between marked variables can be bounded as follows. For any $u \in \mathcal{V}_m$, $S \subseteq \mathcal{V}_m \setminus \{u\}$, and $\Lambda_S \colon S \to \{\mathsf{F}, \mathsf{T}\}$, we have, for $\tau = {{  \left.\kern-\nulldelimiterspace   \mu_{\Omega^{\Lambda_S}}     \right|_{\mathcal{V}_a}   }}$, $$\sum_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S}(u \to v) \right| \le \frac{2}{k 2^{\delta k}} \mathbb{E}_{\Lambda_a \sim \tau} \big[ \left| \{v \in \mathcal{V}_m \setminus S : u\text{ and }v\text{ are connected in }\Phi^{\Lambda_S\cup\Lambda_a} \}\right| \big].$$ </span>

\[lem:expectation:proof\] By the law of total probability, the definition of $\mathcal{I}^{\Lambda_S}(u \to v)$, see , and the definition of $\tau$, for any $v \in \mathcal{V}_m \setminus S$ we have $$\begin{aligned}
      \mathcal{I}^{\Lambda_S}(u \to v) & = \sum_{\Lambda_a \colon \mathcal{V}_a \to \{\mathsf{F}, \mathsf{T}\}} \pr_{\mu_\Omega} \left(\left. \Lambda_a \right| \Lambda_S \right) \left( \pr_{\mu_\Omega}\left( v \mapsto \mathsf{T} \vert u \mapsto \mathsf{T}, \Lambda_S, \Lambda_a\right) - \pr_{\mu_\Omega}\left( v \mapsto \mathsf{T}  \vert u \mapsto \mathsf{F}, \Lambda_S, \Lambda_a\right) \right)  \\
      & = \sum_{\Lambda_a \colon \mathcal{V}_a \to \{\mathsf{F}, \mathsf{T}\}} \pr_{\mu_\Omega} \left(\left. \Lambda_a \right| \Lambda_S \right)  \mathcal{I}^{\Lambda_S \cup \Lambda_a}(u \to v) \\
       & = \sum_{\Lambda_a \colon \mathcal{V}_a \to \{\mathsf{F}, \mathsf{T}\}} \pr_{\tau} \left( \Lambda_a\right)  \mathcal{I}^{\Lambda_S \cup \Lambda_a}(u \to v) .
    \end{aligned}$$ Aggregating over all $v \in \mathcal{V}_m \setminus S$ and applying the triangle inequality we obtain $$\begin{aligned}        
      \sum_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S}(u \to v) \right| & \le \sum_{v \in \mathcal{V}_m \setminus S} \quad \sum_{\Lambda_a \colon \mathcal{V}_a \to \{\mathsf{F}, \mathsf{T}\}} \pr_{\tau} \left( \Lambda_a\right)  \left| \mathcal{I}^{\Lambda_S \cup \Lambda_a}(u \to v) \right|.
    \end{aligned}$$ We note that right-hand side of the inequality above is an expectation over $\Lambda_a \sim \tau$, so $$\begin{aligned}        
      \sum_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S}(u \to v) \right| & \le \mathbb{E}_{\Lambda_a \sim \tau} \left[ \sum\nolimits_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S \cup \Lambda_a}(u \to v) \right| \right].  
    \end{aligned}$$ Finally, we bound $\left| \mathcal{I}^{\Lambda_S \cup \Lambda_a}(u \to v) \right|$ for any $v$ and $\Lambda_a$. Let $\Lambda = \Lambda_S \cup \Lambda_a$. We note that if $u$ and $v$ are not in the same connected component of $G_{\Phi^\Lambda}$, then $\pr_{\mu_{\Omega}}( v \mapsto \mathsf{T} \vert u \mapsto \mathsf{T}, \Lambda ) = \pr_{\mu_{\Omega}}( v \mapsto \mathsf{T}  \vert u \mapsto \mathsf{F}, \Lambda)$, so $\mathcal{I}^{\Lambda}(u \to v) = 0$. Otherwise, by the triangle inequality and Proposition \[prop:marginals\], we have $$\begin{aligned}
      \left|  \mathcal{I}^{\Lambda}(u \to v) \right| & \le \lvert  \pr_{\mu_{\Omega}} ( v \mapsto \mathsf{T} \vert u \mapsto \mathsf{T}, \Lambda ) - 1/2  \rvert + \lvert 1/2 -  \pr_{\mu_{\Omega}}( v \mapsto \mathsf{T}  \vert u \mapsto \mathsf{F}, \Lambda ) \rvert \\ 
    & \le \exp \left( \frac{1}{k 2^{\delta k}} \right) - 1.
    \end{aligned}$$ Applying the inequality $e^z \le 1+2z$ for $z \in (0,1)$, we conclude that $\left|  \mathcal{I}^{\Lambda}(u \to v) \right| \le 2 / (k 2^{\delta k})$. Hence, we have $$\mathbb{E}_{\Lambda_a \sim \tau} \left[ \sum\nolimits_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S \cup \Lambda_a}(u \to v) \right| \right] \le \frac{2}{k 2^{\delta k}} \mathbb{E}_{\Lambda_a \sim \tau} \big[ \left| \{v \in \mathcal{V}_m \setminus S : u\text{ and }v\text{ are connected in }\Phi^{\Lambda_S\cup\Lambda_a} \}\right| \big]$$ and the result follows.

<span> There is an integer $k_0 \ge 3$ such that for any integer $k \ge k_0$ and any density $\alpha$ with $\density \le 2^{rk}$ 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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$, the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m}   }}$ is $(2^{-(\delta/2) k} \log n)$-spectrally independent.</span>

\[lem:si:proof\] Let $u \in \mathcal{V}_m$, $S \subseteq \mathcal{V}_m \setminus \{u\}$ and $\Lambda_S \colon S \to \{\mathsf{F}, \mathsf{T}\}$. We write $\tau = {{  \left.\kern-\nulldelimiterspace   \mu_{\Omega^{\Lambda_S}}     \right|_{\mathcal{V}_a}   }}$ as in Lemma \[lem:expectation\] to simplify the writing. The distribution $\tau$ on assignments to auxiliary variables is $(1/k)$-uniform by Lemmas \[lem:marking\] and \[lem:marginals\]. We apply Lemma \[lem:cc-general\] with $V = \mathcal{V}_a$, $\mu = \tau$, $\rho = 0$, $b = 4 k^4$ and $L = \lceil 2 k^4 \log n \rceil$ to conclude that $\pr_{\Lambda_a \sim \tau} \left( \mathcal{F} \right) \le 2^{-\delta k L}$, where $\mathcal{F}$ is the event that there is a set of clauses $Y$ connected in $G_\Phi$ with $\lvert Y \rvert \ge L$ such that all clauses in $Y$ are unsatisfied by $\Lambda_a \sim \tau$. Therefore, with probability at least $1 - 2^{-\delta k L}$ over the choice of $\Lambda_a \sim \tau$, the connected component of all clauses containing $u$ in $G_{\Phi^{\Lambda_a}}$ has size less than $L$. As assigning values to more variables decreases the size of the connected components, we find that for $\Lambda_a \sim {{  \left.\kern-\nulldelimiterspace   \mu_{\Omega^{\Lambda_S}}     \right|_{\mathcal{V}_a}   }}$ with probability at least $1 - 2^{-\delta k L}$, the connected component of clauses containing $u$ in $G_{\Phi^{\Lambda_S \cup \Lambda_a}}$ has size at most $2k^4 \log n$. If a set of clauses $Y$ has size at most $2 k^4 \log n$, then $\lvert \var(Y) \rvert \le 2 k^5 \log n$.

Since $L \ge 2k^4 \log n$, we note that $2^{-\delta k L} \le n^{-3}$ for large enough $k$. Hence, as a consequence of Lemma \[lem:expectation\], for large enough $k$, we obtain $$\begin{aligned} 
        \sum_{v \in \mathcal{V}_m \setminus S}  \left| \mathcal{I}^{\Lambda_S}(u \to v) \right| &\le \frac{2}{k 2^{\delta k}} \mathbb{E}_{\Lambda_a \sim \tau} \big[ \left| \{v \in \mathcal{V}_m \setminus S : u\text{ and }v\text{ are connected in }\Phi^{\Lambda_S\cup\Lambda_a} \}\right| \big]\\ 
     &  \le \frac{2}{k 2^{\delta k}} \left[\left(  1 - 2^{-\delta k L}  \right) 2 k^5  \log n + 2^{-\delta k L} n \right] \le \frac{4 k^4}{ 2^{\delta k}} \log n + 1 \le 2^{-(\delta/2) k} \log n,
        \end{aligned}$$ and the result follows by applying .

Mixing time of the $\rho$-uniform-block Glauber dynamics {#sec:mixing-time:mt}
--------------------------------------------------------

Finally, we combine the results in this section with Lemma \[lem:block-glauber\] to complete the proof of Lemma \[lem:mixing-time\].

\[rem:marginally-bounded\] The distribution ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m}   }}$ on assignments of the marked variables (Definition \[def:marginal\]) is $b$-marginally bounded for $b = 1 - (1/2)\exp(1/k)$ by Proposition \[prop:marginals\] (or, equivalently, Lemmas \[lem:marking\] and \[lem:marginals\]). Since $\exp(1/k) \le 1 + 2/k$, we have $b \ge 1/2 - 1/k \ge 1/e$ for $k \ge 8$.

<span> There is a function $k_0(\theta) = \Theta(\log(1/\theta))$ such that, for any $\theta \in (0,1)$, for any integer $k \ge k_0(\theta)$ and any density $\alpha$ with $\density \le 2^{rk}$ 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}_m, \mathcal{V}_a, \mathcal{V}_c)$ of $\Phi$ and for $\rho = \lceil 2^{-k-1} \lvert \mathcal{V}_m \rvert \rceil$, the $\rho$-uniform-block Glauber dynamics for updating the marked variables has mixing time $T_{mix}(\rho, \varepsilon/2) \le T := \mtdef$.</span>

\[lem:mixing-time:proof\] In view of Lemma \[lem:si\], w.h.p. over the choice of $\Phi$, the distribution ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$ is $\eta$-spectrally independent for $\eta = 2^{-(\delta/2)k} \log n$, where $\delta = \deltadef$. Moreover, this distribution is $b$-marginally bounded for $b = 1/e$ when $k \ge 8$. We are going to apply Lemma \[lem:block-glauber\] with $V = \mathcal{V}_m$, $\mu = {{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}$, $M = \lvert \mathcal{V}_m \rvert$ and $\kappa = 2^{-k-1}$. First, we check that the hypothesis $M \ge \frac{2}{\kappa} (4\eta / b^2 + 1)$ of Lemma \[lem:block-glauber\] holds. By Corollary \[cor:size-r-distributed\], we have $M \ge (r_0 - \delta) (k \alpha/\Delta) n = \Omega(n)$, so $M \ge \frac{2}{\kappa} (4\eta / b^2 + 1)$ holds for large enough $n$ as $\frac{2}{\kappa} (4\eta / b^2 + 1) = O(\log n)$. Hence, we can apply Lemma \[lem:block-glauber\] to obtain $$\begin{aligned}
      T_{mix}(\rho, \varepsilon/2) & \le \left\lceil C_\rho \frac{M}{\rho} \left( \log \log \frac{1}{\mu_{\min}} + \log \frac{2}{\varepsilon^2} \right) \right\rceil,
    \end{aligned}$$ where $C_\rho = \left(2/\kappa \right)^{4 \eta / b^2 + 1}$. We have $$C_\rho = \exp \left( (\log 2) (k+2) \Big(\frac{4 \eta}{b^2} + 1\Big)  \right)\le 2^{k+2} \exp \left( \frac{(\log 2)(\log n) (k+2) 4 e^2 }{2^{(\delta/2) k}}  \right),$$ so there exists a function $k_0(\theta) = \Theta(\log(1/\theta))$ such that when $k \ge k_0(\theta)$, we have $C_\rho \le 2^{k+ 2} n^\theta$. In light of Remark \[rem:marginally-bounded\], we have $\mu_{\min} \ge b^M$, so $\log \log (1/ \mu_{\min}) \le \log (M \log(1/b) )= \log M$ as $b =1/e$. Thus, we conclude that $$T_{mix}(\rho,\varepsilon/2) \le \left\lceil 2^{2k+ 3} n^\theta  \left( \log M + \log \frac{2}{ \varepsilon^2} \right)  \right\rceil \le \left\lceil 2^{2k+3} n^\theta \log \frac{2n}{\varepsilon^2}\right\rceil. \qedhere$$

Proof of Theorem \[thm:sampling\] {#sec:alg}
=================================

In this section we complete the proof of Theorem \[thm:sampling\]. The proofs in this section do not present any challenging steps. In fact, they amount to combining the main technical results that have already been proved in this work. We start by showing that the calls to the method $\operatorname{Sample}$ in Algorithm \[alg:main\] are unlikely to ever return error, that is, the connected components of $G_{\Phi^{\Lambda}}$ have size at most $2k^4(1+\xi)\log(n)$ almost every time the method is called. As pointed out in our proof outline, this is a straightforward consequence of Lemma \[lem:cc-general\] and the fact that the probability distribution of the output of the Glauber dynamics is $(1/k)$-uniform (Corollary \[cor:marginals:glauber\]).

\[lem:cc\] <span> Let $\theta \in (0,1)$. There is an integer $k_0 \ge 3$ such that, for any integers $k \ge k_0$, $\xi \ge 1$ and any density $\density \le \densitymaindef$, the following holds w.h.p. over the choice of $\Phi = \Phi(k, n, \lfloor \density n\rfloor)$. In the execution of Algorithm \[alg:main\] with input $\Phi$, with probability at least $1 - n^{-3\xi}$ over the random choices made by Algorithm \[alg:main\], every time that the algorithm calls the method $\operatorname{Sample}(\Phi^\Lambda, S)$, the connected components of $G_{\Phi^{\Lambda}}$ have size at most $2k^4(1+\xi)\log(n)$.</span>

\[lem:cc:proof\] Let $\varepsilon = n^{-\xi}$ and let $T = \mtdef$ be the mixing time established in Lemma \[lem:mixing-time\]. We assume that $k$ is large enough so that $2^{rk} \le \alpha_0 = \densitydef$. Algorithm \[alg:main\] calls the method $\operatorname{Sample}$ exactly $T+1$ times in total: $T$ times in line $7$ (when simulating the $\rho$-uniform-block Glauber dynamics) and one time in line $10$ to extend the assignment $X_T$ of marked variables to all variables.

Let $t \in \{0,1,\ldots, T\}$ and let $\pi_t$ be the probability distribution of $X_t$, where $X_t$ is the state of the $\rho$-block-uniform Glauber dynamics on the marked variables described in Algorithm \[alg:main\] after $t$ steps. Recall that $\rho = \lceil 2^{-k-1} \lvert \mathcal{V}_m \rvert \rceil$ and that $X_0$ is chosen jessicabrown@example.net. First, we focus on the case $t < T$. We are going to apply Lemma \[lem:cc-general\] with $a = 2k ^4$, $b = 2 a (1+\xi)$, $V = \mathcal{V}_m$, $\mu = \pi_t$ and this choice of $\rho$. The set $\mathcal{V}_m$ is $r_0$-distributed by the definition of $r_0$-marking (Definition \[def:distributed-marking\]). Moreover, $\pi_t$ is $(1/k)$-uniform by Corollary \[cor:marginals:glauber\], and we have $\rho \le \lvert \mathcal{V}_m \rvert/2^k$. Hence, we can indeed apply Lemma \[lem:cc-general\]. Consider the following experiment described in Lemma \[lem:cc-general\] for $L = \lceil a (1+\xi) \log n \rceil$, which satisfies $a \log n \le L \le b \log n$. First, draw $S \subseteq \mathcal{V}_m$ from the uniform distribution $\tau$ over subsets of $\mathcal{V}_m$ with size $\rho$. Then, sample an assignment $\Lambda_{t+1}$ from ${{  \left.\kern-\nulldelimiterspace   \mu     \right|_{\mathcal{V}_m \setminus S}   }}$, the marginal of $\mu$ on $\mathcal{V}_m \setminus S$. Denote by $\mathcal{F}$ the event that that there is a connected set of clauses $Y$ of $\Phi$ with $\lvert Y \rvert \ge  L$ such that all clauses in $Y$ are unsatisfied by $\Lambda_{t+1}$. Then we have $$\label{eq:prob-error}
    \pr_{S \sim \tau} \left( \pr_{\Lambda_{t+1} \sim {{  \left.\kern-\nulldelimiterspace   \pi_t     \right|_{\mathcal{V}_m \setminus S}   }}} \left( \mathcal{F} \right) \le 2^{- \delta k L}  \right) \ge 1 - 2^{-\delta k L}.$$ Alternatively, this experiment is the same as first sampling an assignment $X_t$ of all variables in $\mathcal{V}_m$ from $\pi_t$, and then restricting the assignment to a random set $S \sim \tau$, obtaining $\Lambda_{t+1}$. Note that this exact experiment occurs before calling the method $\operatorname{Sample}$ in the $t$-th step of the $\rho$-uniform-block Glauber dynamics in Algorithm \[alg:main\]. Thus, in light of , the probability that in step $t+1$ of the execution of Algorithm \[alg:main\] the graph $G_{\Phi^{\Lambda_{t+1}}}$ has a connected component with size at least $L$ is at most $2^{-\delta k L}+2^{-\delta k L}$, where the first $2^{-\delta k L}$ comes from the probability of choosing a wrong set $S \sim \tau$ in and the second $2^{-\delta k L}$ comes from the bound on the probability of the event $\mathcal{F}$ once we have chosen $S$. We have shown that with probability at least $1- {2\cdot} 2^{- \delta k L}$, all the connected components of the graph $G_{\Phi^{\Lambda_{t}}}$ appearing in step $t+1$ of the execution of Algorithm \[alg:main\] have size less than $L$. We have $ {2 \cdot} 2^{- \delta k L} \le n^{- \delta k a (1+\xi) \log 2} \le n^{-5 \xi}$ for large enough $k$, so the probability that $\operatorname{Sample}$ returns error at step $t+1$ is at most $n^{-5\xi}$. The case $t = T$ is analogous, the only difference here is that we call $\operatorname{Sample}$ on $\Phi^{X_T}$, where $X_T \sim \pi_T$ is an assignment of all marked variables, so we apply Lemma \[lem:cc-general\] with $\rho = 0$.

Finally, we carry out a union bound over $t \in \{0, 1, \ldots, T\}$, so the probability that any of the calls to $\operatorname{Sample}$ returns error is at most $(T+1) n^{-5\xi} \le n^{-3\xi}$ for large enough $n$ as $T = O(n^\theta \log n) = O(n \log n)$.

Once we have established Lemmas \[lem:mixing-time\], \[lem:sample\], and \[lem:cc\], the proof of Theorem \[thm:sampling\] follows as below.

Let $r := \rmain$. For any real $\theta \in (0,1)$, there is an integer $k_0 \ge 3$ with $k_0 = O(\log(1/\theta) )$ such that, for any integers $k\ge k_0$ and $ \xi \ge 1$, and for any positive real $\alpha \le \densitymaindef$, 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$.

\[thm:sampling:proof\] Let $k_0(\theta) = \Theta(\log (1/\theta))$ be large enough so that, for all integers $k \ge k_0(\theta)$, $\xi \ge 1$ and all densities $\alpha \le 2^{rk}$, the conclusions of Lemmas \[lem:mixing-time\], \[lem:sample\], and \[lem:cc\] hold w.h.p. over the choice of the random $k$-CNF formula $\Phi = \Phi(k, n, \lfloor \alpha n \rfloor)$. These lemmas are enough to analyse Algorithm \[alg:main\] and tackle this proof. We analyse the distribution $\mu_{alg}$ of the output of Algorithm \[alg:main\]. This distribution outputs either a satisfying assignment of the input formula $\Phi$ or $\textit{error}$. Let $\epsilon = n^{-\xi}$. Let $\mathcal{E}$ be the event that running Algorithm \[alg:main\] outputs $\textit{error}$. This happens with probability at most $\varepsilon/4$ when computing the marking $(\mathcal{V}_m, \mathcal{V}_a, \mathcal{V}_c)$ in line 2 of the algorithm, and in lines 7 and 10 if the method $\operatorname{Sample}(\hat{\Phi}, S)$ returns error, which occurs when $G_{\hat{\Phi}}$ has a connected component with size more than $2k^4(1+\xi)\log(n)$. In view of Lemma \[lem:cc\], the probability that Algorithm \[alg:main\] outputs *error* due to the failure of the method $\operatorname{Sample}$ is at most $n^{-3\xi}=\varepsilon^3$. We conclude that the probability that the algorithm outputs error is bounded above by $\varepsilon / 4 + \varepsilon^3 \le \varepsilon / 2$ . Let $\mu_{Glauber}$ be the distribution that Algorithm \[alg:main\] would output if there were no errors (that is, the distribution assuming that the method Sample always outputs from the appropriate distribution). Then $d_{TV}(\mu_{alg}, \mu_{Glauber})$ is the probability that an error occurs, which is at most $\varepsilon / 2$. Let $\pi_{Glauber}$ be the distribution output by the $\rho$-uniform-block Glauber dynamics on $\mathcal{V}_m$ after $T$ steps. By Lemma \[lem:mixing-time\] on the mixing time of the Glauber dynamics, we have $d_{TV}(\pi_{Glauber}, {{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}) \le \varepsilon / 2$. As $\mu_{Glauber}$ comes from sampling an assignment $X_T$ from $\pi_{Glauber}$ and then completing $X_T$ to all $\mathcal{V}$ by sampling from $\mu_{\Omega}(\cdot \vert X_T)$, we have $d_{TV}(\mu_{Glauber}, \mu_{\Omega}) \le d_{TV}(\pi_{Glauber}, {{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m}   }}) \le \varepsilon/2$. We find that $d_{TV}(\mu_{alg}, \mu_\Omega) \le d_{TV}(\mu_{alg}, \mu_{Glauber}) + d_{TV}(\mu_{Glauber}, \mu_\Omega) \le  \varepsilon / 2 + \varepsilon / 2 = \varepsilon$ as we wanted. The running time of Algorithm \[alg:main\] is now easily obtained by adding up the running times of the following subroutines. The good clauses and good variables are computed in time $O(n + k m) = O(n)$, see Proposition \[prop:bad\]. The marking $(\mathcal{V}_{m}, \mathcal{V}_{a}, \mathcal{V}_c)$ is computed with probability at least $1-\varepsilon/4$ in time $O(n \mdeg k^2 \log(4/\varepsilon)) = O(n \log n)$, see Lemma \[lem:marking\]. Recall that there are $T+1 = O(n^\theta \log (n/\varepsilon^2) ) =  O(n^{\theta} \log n )$ calls to the method $\operatorname{Sample}(\Phi', S)$, and each call takes time $O(\vert S \rvert \log n) = O(n \log n)$ by Lemma \[lem:sample\]. We conclude that the running time of Algorithm \[alg:main\] is $O(n^{1+\theta} \log(n)^2 )$. The result now follows by choosing $k_1 = k_0(\theta/2)$, so the running time for $k \ge k_1$ is $O(n^{1+\theta/2} \log(n)^2 ) = O(n^{1+ \theta})$.

We have now proved that it is possible to (approximately) sample uniformly at random from the satisfying assignments of $\Phi = \Phi(k, n, \lfloor \alpha n \rfloor)$. At this point, standard techniques can be applied to obtain a randomised approximation scheme for counting the satisfying assignments of $\Phi$. These techniques are based on the self-reducibility of $k$-SAT @jerrum1986. The following remark shows how to obtain a randomised approximation scheme that runs in time $O(n^\theta (n/\varepsilon)^2)$ following @feng2020 [Chapter 7], where the authors base their counting algorithm on the simulated annealing method @stefankovic2009 [@huber2015; @kolmogorov2018].

\[Approximate counting for random $k$-SAT formulas\] \[rem:counting\] Let $k_0(\theta)$ be the integer depending on $\theta \in(0,1)$ obtained in Theorem \[thm:sampling\]. Let $k_1 = k_0(\theta/2)$, let $k \ge k_1$ be an integer, let $\xi$ be a positive integer and let $\alpha \le 2^{rk}$ be a density. We apply Theorem \[thm:sampling\] to obtain an algorithm to sample from the satisfying assignments of $\Phi = \Phi(k, n, \lfloor \alpha n \rfloor )$ within $n^{-4\xi}$ total variation distance from the uniform distribution. This algorithm runs in time $O(n^{1+\theta/2})$ and succeeds w.h.p. over the choice of $\Phi$.

Let $\varepsilon \in (0,1)$ with $\varepsilon \ge n^{-\xi}$. A modified version of the approximate counting algorithm of @feng2020 [Section 7], using $O(\varepsilon^{-2} n \log (n / \varepsilon))$ samples from the sampling algorithm above, approximates the number of satisfying assignments of the $k$-CNF formula $\Phi$ with multiplicative error $\varepsilon$, thus, achieving running time $O(n^{\theta/2} (n/\varepsilon)^2 \log(n/\varepsilon)) = O(n^\theta (n/\varepsilon)^2)$. Here we describe these minor modifications.

Let $\Omega_{bad}$ be the set of assignments $X \colon \mathcal{V} \to \{\mathsf{F},\mathsf{T}\}$ that satisfy the bad clauses of $\Phi$. For $X \in \Omega_{bad}$, we define $F(X)$ to be the set of good clauses that are not satisfied by $X$. For $\kappa \in \mathbb{R}$, we define $w_\kappa(X) = \exp(- \kappa \lvert F(X) \rvert )$ and we define the partition function $Z(\kappa) = \sum_{X \in \Omega_{bad}} w_\kappa(X)$. The simulated annealing algorithm of @feng2020 [Section 7] uses $Z(\kappa)$ (with $\Omega^*$ from Definition \[def:subformula\] in place of $\Omega_{bad}$) to approximate the number of satisfying assignments of $\Phi$. We note that $Z(0) = \lvert \Omega_{bad} \rvert$, which can be computed in linear time in $n$ using the exact counting algorithm given in Proposition \[prop:counting\]. Here one has to use the fact that the connected components of $G_{\Phi'}$ for the formula $\Phi' = (\mathcal{V}, \bc)$ have size at most $2k^4 \log n$, see Lemma \[lem:bad-component\] from Appendix \[sec:ap:bad\] and Lemma \[lem:bound-Y\], and the fact that these connected component have tree-excess upper bounded as a function of $k$ (Lemma \[lem:tree-excess\]). Once one has performed these modifications, the algorithm given in  @feng2020 [Section 7] applies without any difficulties.

Proof of Lemma \[lem:bad\] {#sec:ap:bad}
==========================

In this section we prove Lemma \[lem:bad\]. Recall that this result is @galanis2019counting [Lemma 8.16] with a less restrictive bound on the density of the formula and a more restrictive definition of good variables/clauses, see Section \[sec:bad\] for details. Moreover, the obtained upper bound on the number of bad clauses in our version of @galanis2019counting [Lemma 8.16] is tighter. The original proof of Lemma \[lem:bad\] given in @galanis2019counting [Section 8] is split into a sequence of results on random formulas. Here we restate some of these results — only those whose statement needs to change as a consequence of our definition of good variables/clauses and the tighter upper bound. We also explain how these changes affect the proofs if any modifications are necessary.

Let us fix some notation first. The results stated in this section only hold for large enough $k$ unless we say otherwise. Moreover, across this section we fix a density $\alpha$ with $\alpha \le \alpha_0 := \densitydef$. We note that in @galanis2019counting $\alpha$ is at most $2^{k/300}/k^3$. However, in the proofs of @galanis2019counting [Section 8], the only properties of $\alpha$ needed are that there is a real number $r_0 \in (0, 1/2)$ such that, for large enough $k$, $\alpha$ is bounded above by $2^{r_0 k}$, and that $\alpha \le \Delta/k^3$, where $\Delta$ is the threshold for the definition of high-degree variables. In our setting we have $r_0 = \rvalue$ and $\Delta = \mdegdef$, so this is not a problem. We need some definitions. For any set of variables $S \subseteq \mathcal{V}$ of $\Phi$, we denote by $\operatorname{HD}(S)$ the set of high-degree variables in $S$. We denote $\mathcal{V}_0 = \operatorname{HD}(\mathcal{V})$.

\[<span>@galanis2019counting [Corollary 8.4]</span>\] \[cor:bt\] W.h.p. over the choice of $\Phi$, for every set of variables $Y$ such that $2 \le \lvert Y \rvert \le n / 2^k$, the number of clauses that contain at least $3$ variables from $Y$ is at most $\lvert Y\rvert$.

This is a consequence of @galanis2019counting [Lemma 35] with $b = 3$ and $t = 2/(b-1) = 1$.

A $k$-CNF formula $\Phi = (\mathcal{V}, \mathcal{C})$ gives rise to a graph $H_\Phi$ with vertices in $\mathcal{V}$ that is defined as follows. Two variables $v_1$ and $v_2$ are adjacent in $H_\Phi$ if there is a clause $c \in \mathcal{C}$ with $v_1, v_2 \in \var(c)$.

\[<span>@galanis2019counting [Lemma 8.8]</span>\]\[lem:hd:upper\] There is a positive integer $k_0$ such that for any integer $k \ge k_0$ and any density $\alpha$ with $\alpha \le \alpha_0$, the following holds w.h.p. over the choice of $\Phi = \Phi(k, n, \lfloor \alpha n \rfloor)$. Every connected set $U$ of variables in $H_\Phi$ with size at least $2 k^4 \log n$ satisfies that $\lvert \hd(U) \rvert \le \frac{1}{2k^3} \lvert U \rvert $.

The proof is that of @galanis2019counting [Lemma 8.8], with the difference that $\delta_0= 1/(2 k^3)$ instead of $\delta_0 = 1/21600$, as the exact value of $\delta_0$ does not play a role in the proof as long as $1/\delta_0 = \operatorname{poly}(k)$.

\[<span>@coja2014 [Lemma 2.4] and @galanis2019counting [Lemma 8.10]</span>\] Let $k \ge 3$ be an integer and let $\alpha$ be a positive real number with $\alpha  \le e^{k/2} / (2 e^2 k^2)$. For any $\varepsilon \in [1/n,1)$ (depending on $n$) such that $\varepsilon <  e^{-3k}$ for all $n$, the following holds w.h.p. over the choice of the random formula $\Phi = \Phi(k, n, \lfloor \alpha n \rfloor)$. Let $Z$ be a set of clauses with size at most $\varepsilon n$ and let $c_1, \ldots, c_l \in \mathcal{C} \setminus Z$ be distinct clauses. For $s \in \{1, 2, \ldots, \ell\}$, let $N_s := \var(Z) \cup \bigcup_{j = 1}^{s-1} \var(c_{j})$. If $\left| \var(c_s) \cap N_s \right| \ge 3$ for all $s \in \{1, 2, \ldots, \ell\}$, then $\ell \le \varepsilon n$.

The proof is almost identical to the proof of @coja2014 [Lemma 2.4]. There are four differences. First, here, as it is also the case in @galanis2019counting [Lemma 44], $\varepsilon$ can depend on $n$. This will arise later in this proof. Second, the proof of @coja2014 [Lemma 2.4] is carried out for the condition $\left| \var(c_s) \cap N_s \right| \ge \lambda$, where $\lambda $ is an integer with $\lambda > 4$. Here we set $\lambda = 3$ and impose stricter hypotheses on $\alpha$ and $\varepsilon$ to compensate for a smaller $\lambda$. Their (more relaxed) hypotheses on $\alpha$ and $\varepsilon$ are $\alpha \le 2^k \log 2$, $\varepsilon \le k^{-3}$ and $\varepsilon^\lambda \le (2e)^{-4k} / e$. Third, we substitute the last inequality of @coja2014 [Equation 4], which is $$\left[ \left(\frac{e m/n}{\varepsilon} \right)^2 \exp(2k) (2k\varepsilon)^\lambda \right]^{\varepsilon n}
      \le  \left[ \left(2 e \right)^{2k}  \varepsilon^{\lambda /2} \right]^{\varepsilon n},$$ by the inequality $$\label{eq:Ns}
    \begin{aligned}
      \left[ \left(\frac{e m/n}{\varepsilon} \right)^2 \exp(2k) (2k\varepsilon)^\lambda \right]^{\varepsilon n}
      & \le  \left[ \left(e m/n \right)^2 \exp(2k) (2k)^3 \varepsilon \right]^{\varepsilon n} \\
      & \le  \left[ \exp(3k -1) \varepsilon \right]^{\varepsilon n},
    \end{aligned}$$ where we used $\lambda = 3$ and $m / n \le \alpha \le e^{k/2} / (2 e^2 k^2) $. Now, as it is done in @galanis2019counting [Lemma 8.10], we distinguish two cases depending on $\varepsilon$. If $\varepsilon \ge 10 (\log n)/ n$, then using this in conjunction with $\varepsilon <  e^{-3k}$, the right hand size of  is bounded by $e^{-\varepsilon n} \le 1/n^{10} = o(1/n)$. If $1/n \le \varepsilon < 10 (\log n)/ n$, then, for large enough $n$, the right hand size of  is bounded above by $\exp(3k-1) \varepsilon = o(1)$. The last difference between the proofs is that our argument works for all $k \ge 3$, whereas the bound @coja2014 [Equation 4] only holds for large $k$.

The remaining results in this section do not need any changes in their original proofs, other than that every time Corollary 8.4, Lemma 8.8 and Lemmas 8.10-8.16 are invoked in @galanis2019counting [Section 8], we use the version given in this appendix instead. We note that the statements of these results are slightly different to their @galanis2019counting [Section 8] versions, and these changes are again due to the fact that we use $\lambda = 3$ instead of $\lambda = k/10$ in the definition of good variables/clauses.

\[<span>@galanis2019counting [Corollary 8.11]</span>\] \[cor:Ns\] W.h.p. over the choice of $\Phi$, the following holds. Let $Z$ be a set of clauses with size at most $2 n / 2^{k^{10}}$ and let $c_1, \ldots, c_l \in \mathcal{C} \setminus Z$ be distinct clauses. For $s \in \{1, 2, \ldots, \ell\}$, let $N_s := \var(Z) \cup \bigcup_{j = 1}^{s-1} \var(c_{j})$. If $\left| \var(c_s) \cap N_s \right| \ge 3$ for all $s \in \{1, 2, \ldots, \ell\}$, then $\ell \le \lvert Z \rvert$.

The proof given in @galanis2019counting [Corollary 8.11] also applies here.

\[<span>@galanis2019counting [Lemma 8.13]</span>\] \[lem:hd:lower\] W.h.p. over the choice of $\Phi$, for any bad component $S$ of variables, we have $\lvert S \rvert \le 2k \lvert \hd(S) \rvert$.

The proof given in @galanis2019counting [Lemma 8.13] applies using our versions of @galanis2019counting [Corollary 8.4 and Corollary 8.11].

\[<span>@galanis2019counting [Lemma 8.14]</span>\] \[lem:bad-component\] W.h.p. over the choice of $\Phi$, every bad component $S$ has size at most $2k^4 \log n$.

The proof given in @galanis2019counting [Lemma 8.14] applies using our versions of @galanis2019counting [Lemma 8.8 and Lemma 8.13].

\[<span>@galanis2019counting [Lemma 8.15]</span>\] \[lem:bad-variables\] W.h.p. over the choice of $\Phi$, for every connected set of $S$ variables with size at least $2 k^4 \log n$, we have $\lvert S \cap \bv \rvert \le \lvert S \rvert / k^2$.

The proof is analogous to that given in @galanis2019counting [Lemma 8.15]. The only differences are that we apply Lemma \[lem:hd:upper\] instead of @galanis2019counting [Lemma 8.8], we apply Lemma \[lem:hd:lower\] instead of @galanis2019counting [Lemma 8.13], and we have $\delta_0 = 1/(2 k^3)$ instead of $\delta_0 = 1 / 21600$.

\[<span>@galanis2019counting [Lemma 8.16]</span>\] <span>There is an integer $k_0 \ge 3$ such that for any integer $k \ge k_0$ and any density $\density \le \alpha_0 = \densitydef$, the following holds w.h.p. over the choice of the random $k$-CNF formula $\Phi = \Phi(k, n, \lfloor \density n\rfloor)$. For every connected set of clauses $Y$ in $G_\Phi$ such that $\lvert \var(Y) \rvert \ge  2k^4  \log n$, we have $\lvert Y \cap \bc \rvert \le  \lvert Y \rvert / k$.</span>

\[lem:bad:proof\] The same proof applies using our versions of @galanis2019counting [Corollary 8.4 and Lemma 8.15].

Proof of Lemma \[lem:block-glauber\] {#sec:ap:mt}
====================================

In this section we collect the results from @Chen2021 that one needs to combine to obtain Lemma \[lem:block-glauber\] on the mixing time of the $\rho$-uniform-block Glauber dynamics.

\[def:entropy-factorisation\] Let $\mu$ be a distribution supported on $\Omega \subseteq [q]^V$. Let $f \colon \Omega \to \mathbb{R}_{\ge 0}$. We denote the entropy of $f$ by $\operatorname{Ent}_\mu(f)$, that is, $\operatorname{Ent}_\mu(f) = \mathbb{E}_{\mu}(f \log f )) - \mathbb{E}_{\mu}(f) \log(\mathbb{E}_{\mu}(f))$ when $\mathbb{E}_{\mu}(f) > 0$, and $\operatorname{Ent}_\mu(f) = 0$ when $\mathbb{E}_{\mu}(f) = 0$. For $S \subseteq V$, we denote $\operatorname{Ent}_\mu^S(f) = \mathbb{E}_{\tau \sim {{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V \setminus S}   }}}\operatorname{Ent}_{\mu}(f \vert \, \tau)$, where $\operatorname{Ent}_{\mu}(f \vert \, \tau)$ is the entropy of $f$ conditioning to the event that the assignment drawn from $\mu$ agrees with $\tau$ in $V \setminus S$.

Let $\rho \in \{1, 2, \ldots, n \}$. We say that $\mu$ satisfies the $\rho$-uniform block factorisation of entropy (with constant $C_\rho$) if for all $f \colon \Omega \to \mathbb{R}_{\ge 0}$ we have $$\frac{\rho}{n} \operatorname{Ent}_\mu(f) \le C_\rho \frac{1}{\binom{n}{\rho}} \sum_{S \in \binom{V}{\rho}} \operatorname{Ent}_\mu^S(f).$$

One of the main results of @Chen2021 is showing that $\mu$ satisfies the $\rho$-uniform block factorisation of entropy when the distribution $\mu$ is $\eta$-spectrally independent and $b$-marginally bounded. In the proof of @bez2021 [Corollary 19] the authors observe that the proof of Lemma \[lem:factorisation-entropy\] also holds when $\eta$ depends on $n$ and, in particular, in the case $\eta = \epsilon \log n$.

\[ <span>@Chen2021 [Lemma 2.4]</span>\] \[lem:factorisation-entropy\] The following holds for any reals $b, \eta > 0$, any $\kappa \in (0,1)$ and any integer $n$ with $n \ge \frac{2}{\kappa} (4\eta / b^2 + 1)$.

Let $q \ge 2$ be an integer, let $V$ be a set of size $n$ and let $\mu$ be a distribution over $[q]^V$. If $\mu$ is $b$-marginally bounded and $\eta$-spectrally independent, then $\mu$ satisfies the $\lceil \kappa n \rceil$-uniform block factorisation of entropy with constant $C = (2/\kappa)^{4 \eta / b^2 + 1}$.

It turns out that one can bound the mixing time of the $\rho$-uniform-block Glauber dynamics when the target distribution $\mu$ satisfies the $\rho$-uniform block factorisation of entropy.

\[<span>See, e.g., @Chen2021 [Lemma 2.6 and Fact 3.5(4)] or @bez2021 [Lemma 17]</span>\] \[lem:block-glauber:mt\] Let $q \ge 2$, $\rho \ge 1$ be integers and $V$ be a set of size $n \ge \rho + 1$. Let $\mu$ be a distribution supported on $\Omega \subseteq [q]^V$ that satisfies the $\rho$-uniform-block factorisation of entropy with multiplier $C_\rho$. Then, for any $\varepsilon > 0$, the mixing time of the $\rho$-uniform-block Glauber dynamics on $\mu$ satisfies, for $\mu_{\min} = \min_{\Lambda \in \Omega} \mu(\Lambda)$, $$T_{mix}(\varepsilon) \le \left\lceil C_\rho \frac{n}{\rho} \left( \log \log \frac{1}{\mu_{\min}} + \log \frac{1}{2 \varepsilon^2} \right) \right\rceil.$$

\[Proof of Lemma \[lem:block-glauber\]\] \[lem:block-glauber:proof\] The proof of Lemma \[lem:block-glauber\] follows directly from combining Lemmas \[lem:factorisation-entropy\] and \[lem:block-glauber:mt\].

Notation and definitions reference {#ap:notation}
==================================

Here we gather the notation and definitions that are used globally in our work. If some notation is not here, then it is only used in one section of our work (and it is defined in that section).

Table of notation
-----------------

  ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  **Notation**      **Description**                                                                                                                                      **Reference**
  ----------------- ---------------------------------------------------------------------------------------------------------------------------------------------------- -----------------------
  $\Phi(k, n, m)$   A random $k$-CNF formula with $n$ variables and $m$ clauses.                                                                                         Section \[sec:intro\]

  $\alpha$          The density of the formula $\Phi$, so $\alpha = m/n$.                                                                                                Section \[sec:intro\]

  $\mathcal{V}$     The set of variables of $\Phi$.                                                                                                                      Section \[sec:intro\]

  $\mathcal{C}$     The set of clauses of $\Phi$.                                                                                                                        Section \[sec:intro\]

  w.h.p.            Stands for "with high probability". & Section \[sec:intro\]\                                                                                         
                    $d_{TV}$ & The total variation distance between two distributions. & Section \[sec:intro\]\                                                          
                    $r$ & The constant $r = \rmain$ determines the density threshold & Definition \[def:degree\]\                                                        
                    & $\alpha \le 2^{rk}$ in Theorem \[thm:sampling\]. &\                                                                                                
                    $\xi$ & Our sampling algorithm has error at most $n^{-\xi}$. & Theorem \[thm:sampling\]\                                                             
                    $r_0$, $\delta$ & $r_0 = \rvalue$ and $\delta = \deltadef$. & Definition \[def:degree\]\                                                             
                    $\Delta$ & The high-degree threshold, set to $\mdegdef$. & Definition \[def:degree\]\                                                                
                    $\alpha_0$ & The density threshold for the existence of an $r_0$-marking, & Definition \[def:degree\]\                                               
                    & set to $\densitydef$. &\                                                                                                                           
                    $\var(c)$ & The set of variables in a clause $c$. & Section \[sec:po:marking\]\                                                                      
                    $\var(S)$ & The set of variables $\bigcup_{c \in S} \var(c)$. & Section \[sec:po:marking\]\                                                          
                    $\gc$, $\bc$ & Good and bad clauses, a partition of $\mathcal{C}$. & Section \[sec:bad\]\                                                            
                    $\gv$, $\bv$ & Good and bad variables, a partition of $\mathcal{V}$. & Section \[sec:bad\]\                                                          
                    $\mathcal{V}_m$, $\mathcal{V}_a$, $\mathcal{V}_c$ & The sets of marked, auxiliary and control variables. & Definition \[def:distributed-marking\]\   
                    $\Omega^*$ & The set of all assignments $\mathcal{V} \to \{\mathsf{F}, \mathsf{T} \}$ & Definition \[def:subformula\]\                               
                    $\Omega$ & The set of satisfying assignments of $\Phi$. & Definition \[def:subformula\]\                                                             
                    $\mu_A$ & The uniform distribution over $A \subseteq \Omega*$. & Definition \[def:subformula\]\                                                      
                    $\Phi^\Lambda$ & The formula $\Phi$ simplified under $\Lambda$. & Definition \[def:subformula\]\                                                     
                    $\mathcal{V}^{\Lambda}$, $\mathcal{C}^{\Lambda}$ & The variables and clauses of $\Phi^\Lambda$ & Definition \[def:subformula\]\                      
                    $\Omega^\Lambda$ & The set of satisfying assignments of $\Phi^\Lambda$. & Definition \[def:subformula\]\                                             
                    ${{  \left.\kern-\nulldelimiterspace   \mu     \right|_{V}   }}$ & The marginal distribution of $\mu$ on $V$. & Definition \[def:marginal\]\         
                    $T_{\mathrm{mix}}(\rho, \varepsilon)$ & The mixing time of the $\rho$-uniform-block Glauber dynamics. & Section \[sec:po:si:block\]\                 
                    $\mathcal{I}^\Lambda(u \to v)$ & The influence of $u$ on $v$ (under $\Lambda$). & Section \[sec:po:si:block\],\                                      
                    $G_\Phi$ & The dependency graph of $\mathcal{C}$. & Definition \[def:graph-phi\]\                                                                    
                    $\Lambda_1 \cup \Lambda_2$ & The combined assignment of $\Lambda_1$ and $\Lambda_2$. & Section \[sec:po:si:results\]\                                
                    $\Phi_{\mathrm{good}}$& The subformula of $\Phi$ with all good variables and good clauses. & Definition \[def:good-phi\]\                            
                    $\Phi_{\mathrm{bad}}$ & The subformula of $\Phi$ with all bad variables and bad clauses. & Definition \[def:good-phi\]                               
  ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Table of definitions 
---------------------

  **Name**                        **Reference**
  ------------------------------- -----------------------------------------------
  high-degree                     Definition \[def:degree\], page 
  $r$-distributed                 Definition \[def:distributed-marking\], page 
  $r$-marking                     Definition \[def:distributed-marking\], page 
  $\varepsilon$-uniform           Definition \[def:uniform\], page 
  $b$-marginally bounded          Section \[sec:po:si:block\], page 
  $\eta$-spectrally independent   Section \[sec:po:si:block\], page 

Table of results {#ap:results}
================

Here we give a list of our results, including a very short description and a reference to the proof of each of them. The results are listed in order so that the proof of each result only uses the results above it.

  **Name**                               **Description**                                                                                                                                          **Proof**
  -------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------
  Lemma \[lem:block-glauber\]            Mixing time of a $\rho$-uniform-block Glauber dynamics.                                                                                                  Appendix \[sec:ap:mt\], page 
  Proposition \[prop:bad\]               Properties of bad variables and bad clauses.                                                                                                             Section \[sec:bad\], page 
  Lemma \[lem:bad\]                      Bound on the number of bad clauses in connected subsets of $G_\Phi$.                                                                                     Appendix \[sec:ap:bad\], page 
  Lemma \[lem:linearity\]                Lower bound for the number of distinct variables in a clause.                                                                                            Section \[sec:marking\], page 
                                         W.h.p. for all $c,c'\in \mathcal{C}$, $\lvert \var(c) \cap \var(c') \rvert \le 2$.                                                                       
  Theorem \[thm:lll\]                    Asymmetric Lovász local lemma.                                                                                                                           Section \[sec:marking\], page 
  Lemma \[lem:chernoff\]                 Chernoff's bounds.                                                                                                                                       Section \[sec:marking\], page 
  Lemma \[lem:marking\]                  Existence of an $r_0$-marking.                                                                                                                           Section \[sec:marking\], page 
  Lemma \[lem:marginals\]                The distribution ${{  \left.\kern-\nulldelimiterspace   \mu_\Omega     \right|_{\mathcal{V}_m \cup \mathcal{V}_a}   }}$ is $(2^{\delta k}/k)$-uniform.   Section \[sec:marking\], page 
  Proposition \[prop:marginals\]         Combination of Lemmas \[lem:marking\] and \[lem:marginals\].                                                                                             Section \[sec:po:marking\], page 
  Corollary \[cor:marginals:glauber\]    The distribution output by the Glauber dynamics on the marked                                                                                            Section \[sec:marking\], page 
                                         variables is $(2^{\delta k}/k)$-uniform.                                                                                                                 
  Corollary \[cor:size-r-distributed\]   Lower bound on the number of marked/auxiliary variables.                                                                                                 Section \[sec:marking\], page 
  Lemma \[lem:tree-excess\]              The tree-excess of logarithmic-sized set of clauses.                                                                                                     Section \[sec:errors\], page 
  Lemma \[lem:bound-Y\]                  Bound on the number of variables in logarithmic-sized sets                                                                                               Section \[sec:errors\], page 
                                         of clauses.                                                                                                                                              
  Lemma \[lem:bound-marked\]             Bound on the number of marked/auxiliary variables in                                                                                                     Section \[sec:errors\], page 
                                         logarithmic-sized set of clauses.                                                                                                                        
  Lemma \[lem:cc-general\]               Our main technical result: bound on the size of the connected                                                                                            Section \[sec:errors\], page 
                                         components of $G_{\Phi^\Lambda}$.                                                                                                                        
  Proposition \[prop:sample-trees\]      Algorithm to compute the number of satisfying assignments of                                                                                             Section \[sec:sample\], page 
                                         $\Phi$ when $G_\Phi$ is a tree.                                                                                                                          
  Proposition \[prop:counting\]          Algorithm to compute the number of satisfying assignments of                                                                                             Section \[sec:sample\], page 
                                         $\Phi$ when $G_\Phi$ has bounded tree-excess.                                                                                                            
  Lemma \[lem:sample\]                   Algorithm used in the method $\operatorname{Sample}$.                                                                                                    Section \[sec:sample\], page 
  Lemma \[lem:expectation\]              Bounding sum of influences by the expected size of a connected                                                                                           Section \[sec:sample\], page 
                                         component of $G_{\Phi^\Lambda}$.                                                                                                                         
  Lemma \[lem:si\]                       Our spectral independence result for ${{  \left.\kern-\nulldelimiterspace   \mu_{\Omega}     \right|_{\mathcal{V}_m}   }}$.                              Section \[sec:mixing-time\], page 
  Lemma \[lem:mixing-time\]              Our mixing time result for the uniform-block Glauber dynamics.                                                                                           Section \[sec:mixing-time\], page 
  Lemma \[lem:cc\]                       Probability of error of the method $\operatorname{Sample}$ in Algorithm \[alg:main\].                                                                    Section \[sec:alg\], page 
  Theorem \[thm:sampling\]               Our main result.                                                                                                                                         Section \[sec:alg\], page 

[^1]: Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK.

[^2]: 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).

[^3]: This author is supported by an Oxford-DeepMind Graduate Scholarship and a EPSRC Doctoral Training Partnership.

[^4]: In @jain2021sampling 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 \le C 2^{0.1742 \cdot k}/ k^2$.

{'source': 'arXiv_out/2206'}