On belief propagation guided decimation for random k-SAT

Introduction and results

Against this gloomy background, it came as a considerable surprise when experiments indicated that certain highly efficient message passing algorithms come within a whisker of the conjectured satisfiability threshold . These algorithms, called Belief Propagation Guided Decimation and Survey Propagation Guided Decimation, were put forward on the basis of the “cavity method”, a very insightful but non-rigorous technique from statistical mechanics . The message passing procedure upon which Belief Propagation Guided Decimation is based has been rediscovered several times in the context of different applications, see Section 1.5 for details. In the physics literature it was originally known under the name “Bethe-Peierls approximation”. By contrast, the message passing technique that underpins Survey Propagation seems to be new. Conceptually, Belief/Survey Propagation Guided Decimation are more sophisticated than the previously studied algorithms by an order of magnitude; we will give a detailed account in Section 1.3. As a consequence, the techniques that were developed to analyze previous algorithms fail dramatically for Belief/Survey Propagation.

2 Unsatisfied with physics

Ever since these stunning experimental results were reported, coming up with a rigorous analysis of the new message passing algorithms has been one of the key challenges in the area of random constraint satisfaction problems (cf. ). The present paper contributes the first such analysis. More specifically, we study the “vanilla” version of Belief Propagation Guided Decimation (‘BPdec’), the simplest but arguably most natural version. We establish a negative result: BPdec fails to find a satisfying assignment w.h.p. for densities $r>\rho\cdot 2^{k}/k$ for a certain absolute constant $\rho>0$. In other words, we prove that, perhaps surprisingly, BPdec does not outperform simpler combinatorial algorithms such as the one from asymptotically.

There is a constant $\rho_{0}>0$ such that for any $k,r$ satisfying

Theorem 1.1 contrasts with the very promising experimental results. The explanation for this is that the experiments were conducted for ‘small’ $k=3,4,5$ . Indeed, already for $k=10$ large-scale experiments are difficult to carry out, because the relevant density $r$ scales exponentially with $k$. Thus, the good experimental performance can be attributed to the value of the constant $\rho_{0}$ in Theorem 1.1. Because the analysis is intricate as is, no attempt has been made to compute (or optimize) $\rho_{0}$.

Since Belief/Survey Propagation guided decimation were suggested , there have been various stabs at explaining the performance of Belief/Survey Propagation Guided Decimation by means of non-rigorous physics arguments . We will review this work in more detail in Section 1.4 below, but roughly speaking the predictions were as follows. In chronological order,

the authors of opined that Belief Propagation Guided Decimation fails for $r>(1+\varepsilon_{k})2^{k}\ln(k)/k$.

More optimistically, it was predicted in that Belief Propagation Guided Decimation will find satisfying assignments efficiently up to $r\sim 2^{k}\ln 2$.

Finally and most pessimistically, according to Belief Propagation Guided Decimation ought to fail for $r>\rho\cdot 2^{k}/k$ for an absolute constant $\rho>0$.

All of these predictions derived from fairly sophisticated statistical mechanics reasoning, and both quote experimental evidence, thereby (unintentionally) highlighting the need for a rigorous analysis. Theorem 1.1 confirms the scenario put forward in , but does not sit well with the predictions from . Furthermore, the present analysis shows that the reasoning from , where the demise of Belief Propagation Guided Decimation was attributed to a certain change in the geometry of the set of satisfying assignments, is off the mark.

A potential objection to a negative result like Theorem 1.1 is that it might hinge on a small detail of the algorithm that could easily be fixed. However, in the sequel we will see that in the regime (1) our analysis refutes a key hypothesis upon which BPdec depends. In other words, we show that BPdec falls victim to a conceptual issue, not a technicality. Furthermore, some of the arguments used to prove Theorem 1.1 may be of independent interest as they can be expected to extend to applications of BP beyond random $k$-SAT. For instance, we develop a technique for tracing BP on certain quasi-random problem instances.

Finally, we point out that Theorem 1.1 has no immediate bearing on the potentially more powerful Survery Propagation algorithm. We will comment on Survey Propagation in Section 1.4 below.

3 The BPdec algorithm

Fix a satisfiable $k$-CNF $\Phi$ on the variables $V=\left\{{x_{1},\ldots,x_{n}}\right\}$. We generally represent truth assignments as maps $\sigma:V\rightarrow\left\{{-1,1}\right\}$, with $-1$ representing ‘false’ and $1$ representing ‘true’. (It turns out that using $\pm 1$ instead of the more common $0,1$ simplifies the description of BP quite a bit.) Let $\mathcal{S}(\Phi)$ denote the set of all satisfying assignments of $\Phi$. The algorithm BPdec is an attempt at implementing the following thought experiment.

Input: A satisfiable $k$-CNF $\Phi$. Result: An assignment $\sigma:V\rightarrow\left\{{-1,1}\right\}$.

A moment’s reflection reveals that the above experiment not only produces a satisfying assignment, but that its (random) outcome is in fact uniformly distributed over the set $\mathcal{S}(\Phi)$. We observe that in the formulas $\Phi_{t}$ obtained at intermediate steps some clauses can (and typically will) have length less than $k$.

Referring to the successive assignments of variables and the corresponding shrinking of the formula, we call the above experiment the decimation process. The obvious obstacle to implementing it is the computation of the marginal probabilities $M_{x_{t+1}}(\Phi_{t})$. Indeed, this task is $\#P$-hard on worst-case inputs.

Yet, under what conditions could we hope to compute (or approximate) the marginals $M_{x}(\Phi_{t})$? Clearly, the marginals are influenced by ‘local’ effects. For instance, if $x$ occurs in a unit clause $a$ of $\Phi_{t}$, i.e., a clause whose other $k-1$ variables have been assigned already without satisfying $a$, then $x$ must be assigned so as to satisfy $a$. Hence, if $x$ appears in $a$ positively, then $M_{x}(\Phi_{t})=1$, and otherwise $M_{x}(\Phi_{t})=0$. Similarly, if $x$ occurs only positively in $\Phi_{t}$, then $M_{x}(\Phi_{t})\geq 1/2$. Furthermore, these local effects propagate: if $x$ appears in a clause $a$ whose other variables $y$ are subject to influences from other clauses $b_{y}\neq a$, then the local effects operating on the variables $y$ may impact $x$ via $a$. In the most extreme case, think of a variable $x$ that occurs in a clause $a$ whose other variables are all constrained by unit clauses to take values that fail to satisfy $a$. Then $a$ effectively turns into a unit clause for $x$.

The key hypothesis underlying BPdec is that in random formulas such local effects determine the marginals $M_{x}(\Phi_{t})$ asymptotically. To define ‘local’ precisely, we need a metric on the variables/clauses. This metric is the shortest path distance on the factor graph $G=G(\Phi_{t})$ of $\Phi_{t}$, which is a bipartite graph whose vertices are the variables $V_{t}=\left\{{x_{t+1},\ldots,x_{n}}\right\}$ and the clauses of $\Phi_{t}$. Each clause is adjacent to the variables that occur in it. For an integer $\omega\geq 1$ let $N^{\left[{\omega}\right]}(x)$ signify the set of all vertices of $G$ that have distance at most $2\omega$ from $x$. Then the induced subgraph $G[N^{\left[{\omega}\right]}(x)]$ corresponds to the sub-formula of $\Phi_{t}^{\left[{\omega}\right]}$ obtained by removing all clauses and variables at distance more than $2\omega$ from $x_{t}$. Note that all vertices at distance precisely $2\omega$ are variables. Hence, any satisfying assignment of $\Phi$ induces a satisfying assignment of the sub-formula. Let us denote by

the marginal probability that $x_{t}$ takes the value $1$ in a random satisfying assignment of this sub-formula.

Of course, in the worst case the ‘local’ marginals $M_{x}^{\left[{\omega}\right]}(\Phi_{t})$ are just as difficult to compute as the $M_{x}(\Phi_{t})$ themselves. But BPdec employs an efficient heuristic called Belief Propagation (‘BP’), which yields certain values $\mu_{x_{t}}^{\left[{\omega}\right]}(\Phi_{t})\in\left[{0,1}\right]$; we will state this heuristic below. If $G[N^{\left[{\omega}\right]}(x_{t})]$ is a tree, then provably $\mu_{x_{t}}^{\left[{\omega}\right]}(\Phi_{t})=M_{x_{t}}^{\left[{\omega}\right]}(\Phi_{t})$ . Moreover, standard arguments show that in a random formula $\vec{\Phi}$ actually $G[N^{\left[{\omega}\right]}(x_{t})]$ is a tree w.h.p. so long as $\omega=o(\ln n)$. More generally, in order to obtain an efficient algorithm it would be sufficient for the BP outcomes $\mu_{x_{t}}^{\left[{\omega}\right]}(\Phi_{t})$ to approximate the true overall marginals $M_{x_{t}}(\Phi_{t})$ well for some (say, polynomially computable, polynomially bounded) function $\omega=\omega(n)\geq 1$. This leads to the following hypothesis underpinning BPdec (cf. ).

With probability $1-o(1)$ over the choice of $\vec{\Phi}$ and the random decisions in Experiment 1.2 the following holds for all $0\leq t<n$.

For any $\varepsilon>0$ there is $\omega=\omega(\varepsilon,k,r)$ such that $|M_{x_{t+1}}(\vec{\Phi}_{t})-M_{x_{t+1}}^{\left[{\omega}\right]}(\vec{\Phi}_{t})|\leq\varepsilon.$

For any $\varepsilon>0$ there is $\omega=\omega(\varepsilon,k,r)$ such that $|M_{x_{t+1}}(\vec{\Phi}_{t})-\mu_{x_{t+1}}^{\left[{\omega}\right]}(\vec{\Phi}_{t})|\leq\varepsilon.$

Hypothesis 1.3 motivates the following algorithm , which is called Belief Propagation Guided Decimation because it combines BP (Step 2) with a decimation step (Steps 3–4).

BPdec$(\Phi)$ Input: A $k$-CNF $\Phi$ on $V=\left\{{x_{1},\ldots,x_{n}}\right\}$. Output: An assignment $\sigma:V\rightarrow\left\{{-1,1}\right\}$.

The function $\omega=\omega(k,r,n)$ is “hard-wired” into the above algorithm, and our analysis does not depend on any assumptions on $\omega$. In particular, the statement of Theorem 1.1 is understood to hold for all integer-valued functions $\omega=\omega(n)\geq 0$.

Although, strictly speaking, Hypothesis 1.3 provides neither a necessary nor a sufficient condition for BPdec to succeed on random $k$-CNFs w.h.p., the hypothesis inspired the algorithm (we will get back to this in Section 1.4). Combining parts of the present analysis of the dynamics of the BP computation (more precisely, Theorem 3.2 below) with techniques for analyzing the geometry of the space of satisfying assignments, we proved the following in .

Both statements of Hypothesis 1.3 are false for $k,r$ satisfying (1).

To complete the presentation of the algorithm, we need to define Belief Propagation for $k$-SAT; for a detailed derivation we point the reader to . Ultimately, we need to define the value $\mu_{x_{t+1}}^{\left[{\omega}\right]}(\Phi_{t})$ in Step 2 of BPdec.

The message space $\mathcal{M}(\Phi_{t})$ is the set of all tuples

for any $x\in V_{t}$, unless the denominator is zero, in which case we set $\mu_{x}^{\left[{\omega}\right]}(\Phi_{t})=\frac{1}{2}$.

BPdec could be called the “vanilla” version of Belief Propagation Guided Decimation. It is the simplest but arguably the most natural variant. Nonetheless, several other installments have been suggested and experimented with. They differ in how the number $\omega$ of iterations is chosen and how exactly the result of the Belief Propagation calculation is used to decimate.

In the “vanilla” variant we used an a priori number $\omega$ of iterations. An alternative idea is to iterate the Belief Propagation operator until it reaches a fixed point. More precisely, to accommodate numerical inaccuracies one could stop after $\omega$ iterations, with $\omega\geq 1$ the least integer such that for some small $\varepsilon>0$ we have

where the maximum is taken over all edges of the factor graph (e.g., ). Unfortunately, it is not generally assured that the convergence criterion (4) will ever be met. Hence, one would need to specify how to proceed otherwise. For instance, one could specify an a priori maximum number of iterations. Our analysis can be adapted easily to accommodate these modifications (details omitted).

More importantly, one could come up with a more sophisticated decimation strategy, i.e., a different way of using the BP result $\mu^{\left[{\omega}\right]}$ to choose the variable to be assigned next and its value. In BPdec we went for the “vanilla rule”: the variables are assigned in the natural order, and each time the assignment is performed randomly based on the BP estimate of the marginal.

But in experiments a more common decimation strategy is the “most biased variable” rule: at each time choose a variable $x\in V_{t}$ that maximizes the “bias” $|\mu_{x}^{\left[{\omega}\right]}(\Phi_{t})-\frac{1}{2}|$, and assign it randomly based on the BP estimate. Experimentally the most biased variable rule allows for slightly better results than the vanilla rule. For instance, in random $4$-SAT, experiments indicate that the former succeeds up to $m/n=9.24$, and the latter up to $m/n=9.05$ .

The statistical mechanics ideas that underpin Belief Propagation guided decimation do not endorse a preference for the “most biased variable” rule over the “vanilla” strategy. But a heuristic argument in favor of “most biased variable” is that it might reduce the effect of numerical errors building up . The present analysis does not seem to extend to “most biased variable” in a straightforward manner. Thus, analyzing it remains an interesting open problem.

Comparison with combinatorial algorithms.

The difference between the previously studied combinatorial algorithms for random $k$-SAT and Belief Propagation can be explained nicely in terms of the factor graph. Indeed, in order to decide upon the value of a variable the previous algorithms only took the clauses and variables at distance two or four into consideration. Based on this information, the variable is assigned following some simple combinatorial rule.

BPdec can be viewed as a systematic way of making a “less shortsighted” decision. The algorithm takes into account clauses/variables at distance up to $2\omega$, where $\omega$ may be a function that grows with $n$. Indeed, the idea of determining the marginal $M_{x_{t+1}}^{\left[{\omega}\right]}(\vec{\Phi}_{t})$ yields a meaningful way of incorporating the data from all these clauses/variables. In particular, BPdec implicitly implements many of the rules that are used in the combinatorial algorithms (e.g., the “Unit Clause” rule). In this sense, BPdec can be seen as a clever generalization of many of these combinatorial algorithms. However, this also means that the techniques used in the previous analyses of combinatorial algorithms are insufficient to tackle BPdec.

4 The statistical physics perspective

Closely following the non-rigorous paper , we discuss in this section the statistical mechanics motivation for BPdec. This will provide the basis for the discussion of the non-rigorous predictions as to the algorithm’s performance.

According to the physicists’ “cavity method”, the random formula $\vec{\Phi}$ undergoes several further phase transitions prior to the satisfiability threshold. These phase transitions affect the correlations between the truth values that can be assigned to different variables. Thus, fix a variable $x$ and let $\omega=\omega(n)=o(\ln n)$ be a function that tends to infinity slowly, say $\omega=\lceil\ln\ln n\rceil$. Furthermore, let $\mathcal{B}$ be the set of all variables at distance exactly $2\omega$ from $x$ in the factor graph. How do the values assigned to variables on the “far away boundary” $\mathcal{B}$ affect the truth value of $x$?

The strongest possible decay of correlations occurs when the boundary $\mathcal{B}$ has no impact on $x$ at all. To formalize this, let $\tau:\rightarrow\left\{{-1,1}\right\}$ be a satisfying assignment of $\vec{\Phi}$ and let $M^{\left[{\omega}\right]}_{x}(\vec{\Phi},\tau)$ be the fraction of all satisfying assignments of $\vec{\Phi}$ that set $x$ to true and that coincide with $\tau$ on $\mathcal{B}$. In symbols,

Also recall that $M_{x}(\vec{\Phi})$ denotes the marginal probability that $x$ takes the value “true” in a random satisfying assignment of $\vec{\Phi}$ (without any boundary condition). The Gibbs uniqueness condition requires that

In words, fixing the “far away” variables does not make it noticeably more or less like for $x$ to take the value “true”. Hence, the marginal $M_{x}(\vec{\Phi})$ is governed entirely by the effects of variables at distance less than $2\omega$ from $x$, i.e., by the local structure of the formula.

Consequently, it seems reasonable to expect that Belief Propagation yields the correct marginals so long as (5) holds. It is known rigorously that w.h.p. (5) holds up to $r\sim r_{u}=2\ln k/k$ (a function that tends to zero for large $k$), and that Belief Propagation does indeed yield the correct marginals for such densities . That is, for $r<r_{u}$ w.h.p.

To define the second correlation decay property, let us denote by $\vec{\tau}$ a uniformly random element of $\mathcal{S}(\vec{\Phi})$. Then the non-reconstruction condition is that

Hence, fixing the far away boundary to a “typical” satisfying assignment has no discernible effect on $x$. Neglecting a $o(1)$-fraction of “atypical” cases $\vec{\tau}$, one might still expect (6) to hold so long as (7) is satisfied. However, this conjecture awaits a rigorous proof. According to the cavity method, (7) holds up to $r\sim r_{d}=2^{k}\ln(k)/k$. Moreover, the best rigorously analyzed algorithm (which is based on local search) succeeds in finding a satisfying assignment in polynomial time right up to $r\sim r_{d}$ w.h.p. .

To state the third property, let us denote the joint distribution of the truth values of the variables $\mathcal{B}$ under a random satisfying assignment by $M_{\mathcal{B}}$. Thus, $M_{\mathcal{B}}$ is a probability distribution over $\left\{{-1,1}\right\}^{{\mathcal{B}}}$. Then the replica symmetry condition requires that the truth values of the variables in $\mathcal{B}$ are asymptotically independent. Formally,

It has duly been conjectured in that (8) suffices to obtain (6), i.e., to ensure that Belief Propagation yields the correct marginals on $\vec{\Phi}$. The cavity method predicts that (8) holds for

while the conjectured satisfiability threshold is

The densities $r_{d},r_{c}$ are also conjectured to mark a change in the geometry of the set $\mathcal{S}(\vec{\Phi})$ of satisfying assignments. Let us turn $\mathcal{S}(\vec{\Phi})$ into a graph by considering $\sigma,\tau\in\mathcal{S}(\vec{\Phi})$ adjacent if their Hamming distance is equal to one. While for densities $r<r_{d}$ the graph $\mathcal{S}(\vec{\Phi})$ is conjectured to be (essentially) connected, for $r_{d}<r<r_{c}$ it shatters into an exponential number of tiny connected components w.h.p. More precisely, $\mathcal{S}(\vec{\Phi})$ admits a decomposition

into “clusters” ${\mathcal{C}}_{i}$ such that $|{\mathcal{C}}_{i}|\leq\exp(-\Omega(n))|\mathcal{S}(\vec{\Phi})|$ for all $i$ and such that any two satisfying assignments in different clusters have Hamming distance $\Omega(n)$. This decomposition was established rigorously in . Intuitively, the cluster decomposition explains why (7) fails to hold for $r>r_{d}$: the conditional marginal $M_{x}^{\left[{\omega}\right]}(\vec{\Phi},\tau)$ corresponds to the marginal of $x$ within the cluster of $\tau$, in contrast to the marginal $M_{x}(\vec{\Phi})$ over the entire set of satisfying assignments.

This structure goes by the name of condensation in physics. The values that different variables take within each cluster ${\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{\gamma}$ are conjectured to be heavily dependent. Furthermore, (11) implies that $M_{\mathcal{B}}$ is but a convex combination of a small (bounded) number of such intra-cluster distributions. Hence, the “condensed” geometry (11) appears to be irreconcilable with the factorization property (8).

Belief Propagation.

Based on this “static” picture, three different hypotheses have been put forward as to the likely performance of Belief Propagation guided decimation. Most optimistically, the authors of argue that Belief Propagation guided decimation ought to find satisfying assignments efficiently for densities right up to $r_{c}$. Their prediction derives from the opinion that (8) should be sufficient to obtain (6), and that (6) is the key to the success of Belief Propagation Guided Decimation. Specifically, refers to the the “most biased variable” variant. However, the precise decimation strategy is irrelevant to their considerations, which are in effect at odds with Theorem 1.1.

A second prediction is that Belief Propagation Guided Decimation should fail to find satisfying assignments for $r>r_{d}$ . This conjecture is based on the hunch that the decomposition of $\mathcal{S}(\vec{\Phi})$ into “clusters” and the ensuing demise of (7) cause (6) to fail. Agreeing with , the authors appear to view (6) as the key to the performance of BPdec.

According to the third prediction , BPdec fails for densities $r>\rho_{0}\cdot 2^{k}/k$, with $\rho_{0}>0$ an absolute constant (independent of $k$). This prediction is based on a non-rigorous analysis of the decimation process, i.e., the idealized thought experiment that BPdec strives to implement (Experiment 1.2). Crucially, the authors of realize that (6) does not guarantee the success of BPdec.

Instead, their analysis indicates that as the decimation process proceeds to assign variables, the remaining unassigned variables are bound by clauses that become shorter and shorter. In effect, the clauses become more and more difficult to satisfy, and thus the remaining set of satisfying assignments shrinks rapidly. In other words, successive decimation of variables has a similar effect as increasing the density of the formula. Consequently, after a number $t$ of decimations BPdec may wind up with a formula $\vec{\Phi}_{t}$ that violates (8) and thus (6), even though the initial formula $\vec{\Phi}$ may well have satisfied those conditions. The contribution supersedes an earlier attempt at studying the effect of decimation .

Theorem 1.1 is in agreement with the prediction from . But an important advantage of the present work over the (non-rigorous) contribution is that here we manage to analyze the actual algorithm BPdec. By contrast, only deals with the decimation process (i.e., Experiment 1.2, the idealized experiment that assumes knowledge of the precise marginals). That is, going significantly beyond the ambition of , here we develop a technique for explicitly analyzing the dynamics of the message passing procedure.

In summary, the predictions in as to the performance of Belief Propagation are inaccurate because they ignore the effect of decimation. By contrast, as conjectured in and proved here, in actuality BPdec gets itself into trouble by assigning and decimating one variable after the other. Thus, computing the correct marginals in the original formula $\vec{\Phi}$ is one thing, but continuing to do so as decimation proceeds is quite another. Let us mention, as a cautionary tale, that both quote experimental evidence to support their claims. This illustrates the difficulty of producing reliable experimental results on large random CSPs, and thus the need for rigorous results.

Survey Propagation.

Let us briefly comment on Survey Propagation guided decimation, the physicists’ flagship algorithm . It is based on the idea of working with a different probability distribution. Namely, instead of the uniform probability over satisfying assignments, Survey Propagation aims for the uniform distribution over the clusters ${\mathcal{C}}_{i}$ in the decomposition (10). These clusters can be encoded as generalized assignments $\tau:V\rightarrow\left\{{-1,0,1}\right\}$, with $\tau(x)=\pm 1$ indicating that variable $x$ takes the value $\pm 1$ in all the assignments in ${\mathcal{C}}_{i}$, and $\tau(x)=0$ indicating that $x$ can take either value . Survey Propagation guided decimation combines a message passing algorithm for approximating the marginals of these generalized assignments with a decimation procedure (see for details).

There is an absolute constant $\rho_{1}>0$ such that the Survey Propagation Guided Decimation algorithm as stated in fails to find a satisfying assignment of $\vec{\Phi}$ w.h.p. for $r>\rho_{1}\cdot 2^{k}/k$.

If true, Conjecture 1 would imply that Survey Propagation Guided Decimation is inferior to conceptually much simpler local-search algorithms (such as ), at least for large clause lengths $k$.

5 Further related work

In full generality, Belief Propagation is a generic technique for computing the marginals of a probability distribution described by an “acyclic graphical model” . But special instantiations of Belief Propagation have been (re)discovered several times for several applications. Examples include statistical inference , coding theory and statistical mechanics , where the method is also referred to as “Bethe-Peierls approximation”. For a coherent discussion see and the references therein.

In spite of BP’s practical success (and popularity), rigorous analyses of the algorithm are scarce. A few exist in the context of LDPC decoding (e.g., ). We also analyzed BP for graph $3$-coloring on a certain class of expander graphs. A further related result deals with the conceptually much simpler Warning Propagation algorithm on certain random 3-CNFs (“planted model”) . In the random $k$-XORSAT problem (random linear equations mod $2$), Belief Propagation reduces to Warning Propagation due to the algebraic nature of the problem and can thus be analyzed easily . Furthermore, there has been some recent progress on analyzing certain variants of BP (such as the “max-product algorithm”) for certain optimization problems that are polynomial-time solvable in the worst case (e.g., ).

The study of the BP marginals on the undecimated random formula $\vec{\Phi}$ is somewhat related to the so-called reconstruction problem. This problem has been studied on ‘symmetric’ random CSPs, which include problems such as (hyper)graph coloring , but not $k$-SAT. The proofs in are based on indirect arguments (related to the second moment method), which do not seem to extend to an analysis of BPdec.

6 Preliminaries and notation

In this section we collect a few well-known results and introduce a bit of notation. First of all, we note for later reference a well-known estimate of the expected number of satisfying assignments (see, e.g., for a derivation).

Furthermore, we are going to need the following Chernoff bound on the tails of a binomially distributed random variable or, more generally, a sum of independent Bernoulli trials [26, p. 21].

Let $X$ be a sum of independent Bernoulli variables with mean $\mu>0$. Let

For a real $b\times a$ matrix $\Lambda$ let

Thus, $\left\|{\Lambda}\right\|_{\squareforqed}$ is the norm of $\Lambda$ viewed as an operator from $\mathbf{R}^{a}$ equipped with the $L^{\infty}$-norm to $\mathbf{R}^{b}$ endowed with the $L^{1}$-norm. For a set $A\subset\left[{a}\right]=\left\{{1,\ldots,a}\right\}$ we let $\vec{1}_{A}\in\{0,1\}^{a}$ denote the indicator vector of $A$. The following well-known fact about the norm $\left\|{\cdot}\right\|_{\squareforqed}$ of matrices with diagonal entries equal to zero is going to come in handy.

For a real $b\times a$ matrix $\Lambda$ with zeros on the diagonal we have

Finally, throughout the paper we let $S_{n}$ denote the set of permutations of $\left[{n}\right]$.

The probabilistic framework for analyzing BPdec

The single most important technique for analyzing algorithms on the random input $\vec{\Phi}$ is the “method of deferred decisions”. Where it applies, the dynamics of the algorithm can typically be traced tightly via differential equations, martingales, or Markov chains. Virtually all of the previous analyses of algorithms for random $k$-SAT are based on this approach . Unfortunately, the ‘deferred decisions’ technique is limited to very simple, ‘shortsighted’ algorithms that decide upon the value of a variable $x$ on the basis of the clauses/variables at distance, say, one or two from $x$ in the factor graph . By contrast, in order to assign some variable $x_{t}$, BPdec explores clauses at distance up to $2\omega$ from $x_{t}$, where (potentially) $\omega=\omega(n)\rightarrow\infty$. This renders a ‘deferred decisions’ approach hopeless.

Therefore, to prove Theorem 1.1 we need a fundamentally different strategy. In the present section we set up the probabilistic framework for the analysis. We will basically reduce the analysis of BPdec to the problem of analyzing the BP operator on the formula that is obtained from $\vec{\Phi}$ by substituting ‘true’ for the first $t$ variables $x_{1},\ldots,x_{t}$ and simplifying (Theorem 2.2 blow). In the next section we will show that this decimated formula enjoys a few simple quasirandomness properties with probability extremely close to one. Finally, we will show that these properties suffice to trace the BP computation.

Applied to a fix, non-random formula $\Phi$ on $V=\left\{{x_{1},\ldots,x_{n}}\right\}$, BPdec yields an assignment $\sigma:V\rightarrow\left\{{-1,1}\right\}$ (that may or may not be satisfying). This assignment is random, because BPdec itself is randomized. Hence, for any fixed $\Phi$ running BPdec$(\Phi)$ induces a probability distribution $\beta_{\Phi}$ on $\left\{{-1,1}\right\}^{V}$. With $\mathcal{S}(\Phi)$ the set of all satisfying assignments of $\Phi$, the ‘success probability’ of BPdec on $\Phi$ is just

Thus, to establish Theorem 1.1 we need to show that in the random formula,

is exponentially small w.h.p. To this end, we are going to prove that the measure $\beta_{\vec{\Phi}}$ is ‘rather close’ to the uniform distribution on $\left\{{-1,1}\right\}^{V}$ w.h.p., of which $\mathcal{S}(\vec{\Phi})$ constitutes only an exponentially small fraction.

To facilitate the analysis, we are going to work with a slightly modified version of BPdec. While the original BPdec assigns the variables in the natural order $x_{1},\ldots,x_{n}$, the modified version PermBPdec chooses a permutation $\pi$ of $\left[{n}\right]$ uniformly at random and assigns the variables in the order $x_{\pi(1)},\ldots,x_{\pi(n)}$. Let $\bar{\beta}_{\Phi}$ denote the probability distribution induced on $\left\{{-1,1}\right\}^{V}$ by PermBPdec$(\Phi)$. Because the uniform distribution over $k$-CNFs is invariant under permutations of the variables, we obtain

Let $\Phi$ be a $k$-CNF and let $\delta>0$. Given a permutation $\pi$ and a partial assignment $\sigma:\left\{{x_{\pi(s)}:s\leq t}\right\}\rightarrow\left\{{-1,1}\right\}$, we let $\Phi_{t,\pi,\sigma}$ denote the formula obtained from $\Phi$ by substituting the values $\sigma(x_{\pi(s)})$ for the variables $x_{\pi(s)}$ for $1\leq s\leq t$ and simplifying. Formally, $\Phi_{t,\pi,\sigma}$ is obtained from $\Phi$ as follows:

remove any empty clauses (resulting from clauses of $\Phi$ that become unsatisfied if we set $x_{\pi(s)}$ to $\sigma(x_{\pi(s)})$ for $1\leq s\leq t$) from the formula.

For a number $\delta>0$ and an index $l>t$ we say that $x_{\pi(l)}$ is $(\delta,t)$-biased if

Moreover, the triple $(\Phi,\pi,\sigma)$ is $(\delta,t)$-balanced if no more than $\delta(n-t)$ variables are $(\delta,t)$-biased.

Let $\pi$ be the permutation chosen by PermBPdec$(\Phi)$, and let $\sigma$ be the partial assignment constructed in the first $t$ steps. The variable $x_{\pi(t+1)}$ is uniformly distributed over the set $V\setminus\left\{{x_{\pi(s)}:s\leq t}\right\}$ of currently unassigned variables. Hence, if $(\Phi,\pi,\sigma)$ is $(\delta,t)$-balanced, then the probability that $x_{\pi(t+1)}$ is $(\delta,t)$-biased is bounded by $\delta$. (This conclusion was the purpose of decimating the variables in a random order.) Furthermore, given that $x_{\pi(t+1)}$ is not $(\delta,t)$-biased, the probability that PermBPdec will assign set it to ‘true’ lies in the interval $\left[{\frac{1}{2}-\delta,\frac{1}{2}+\delta}\right]$. Consequently,

Thus, the smaller $\delta$, the closer $\sigma(x_{\pi(t+1)})$ comes to being uniformly distributed. Hence, if $(\delta,t)$-balancedness holds for all $t$ with a ‘small’ $\delta$, then $\bar{\beta}_{\Phi}$ will be close to the uniform distribution on $\left\{{-1,1}\right\}^{V}$.

To put this observation to work, we define

where $c>0$ is a small enough absolute constant Setting $c=10^{-10^{10}}$ will evidently suffice, but no attempt at finding the optimal $c$ has been made.. In addition, we let

Furthermore, $\Delta_{\hat{t}}\sim\frac{n}{ck}\left[{(kr/2^{k})^{-c}-\exp(-ck)}\right]$.

Since $\exp(ck/n)=1+ck/n+O(n^{-2})$ and ${\hat{t}}=\Omega(n)$, we obtain from (15)

Furthermore, for $1\leq t\leq{\hat{t}}$ equation (15) yields the upper bound

For $\xi>0$ we say that $\Phi$ is $(t,\xi)$-uniform if

Proceeding by induction on $t$, we are going to use (12) to relate the distribution $\bar{\beta}_{\Phi}$ to the uniform distribution on $\left\{{-1,1}\right\}^{V}$ for $(t,\xi)$-uniform formulas. More precisely, in Section 2.2 we are going to prove

Suppose that $\Phi$ is $(t,\xi)$-uniform for all $0\leq t\leq{\hat{t}}$. Then

Proposition 1 reduces the proof of Theorem 1.1 to showing that $\vec{\Phi}$ is $(t,\xi)$-uniform with some appropriate probability.

To prove this, we need two simple definitions. We call a clause $a$ of a formula $\Phi$ redundant if $\Phi$ has another clause $b$ such that $a,b$ have at least two variables in common. Furthermore, we call the formula $\Phi$ tame if

$\Phi$ has no more than $\ln n$ redundant clauses, and

no more than $\ln n$ variables occur in more than $\ln n$ clauses of $\Phi$.

The random formula $\vec{\Phi}$ is tame w.h.p.

Now, the following result provides the key estimate for proving that $\vec{\Phi}$ is $(t,\xi)$-uniform with a very high probability.

There is a constant $\rho_{0}>0$ such that for any $k,r$ satisfying $2^{k}\rho_{0}/k\leq r\leq 2^{k}\ln 2$ there is $\xi=\xi(k,r)>0$ so that for $n$ large enough the following holds. Fix any permutation $\pi$ of $\left[{n}\right]$ and any assignment $\sigma\in\left\{{-1,1}\right\}^{V}$. Then for any $0\leq t\leq{\hat{t}}$ we have

We defer the proof of Theorem 2.2 to Section 3.

For $1\leq t\leq{\hat{t}}$ and a $k$-CNF $\Phi$ we let $X_{t}(\Phi)$ signify the number of pairs $(\pi,\sigma)\in S_{n}\times\left\{{-1,1}\right\}^{V}$ such that $(\Phi,\pi,\sigma)$ fails to be $(\delta_{t},t)$-balanced. Then Theorem 2.2 yields

Hence, by Markov’s inequality and the union bound

Since $\vec{\Phi}$ is $(t,\xi)$-uniform if $X_{t}(\Phi)\leq 2^{n}n!\cdot\exp(-\xi n-10\Delta_{t})$, the assertion follows from (18). ∎

Recalling that $\rho=kr/2^{k}$, we thus obtain

Hence, if $\rho\geq\rho_{0}$ for a sufficiently large constant $\rho_{0}>0$, then (20) yields $\bar{\beta}_{\vec{\Phi}}(\mathcal{S}(\vec{\Phi}))=\exp(-\Omega(n))$. Finally, Theorem 1.1 follows from Fact 2.1. ∎

2 Proof of Proposition 1

We consider an additional variant of BPdec that receives the order $\pi$ in which variables are to be decimated as an input parameter.

BPdec$(\Phi,\pi)$ Input: A $k$-SAT formula $\Phi$ on $V=\left\{{x_{1},\ldots,x_{n}}\right\}$ and a permutation $\pi\in S_{n}$. Output: An assignment $\tau:V\rightarrow\left\{{-1,1}\right\}$.

Fix a $k$-CNF $\Phi$ that is $(t,\xi)$-uniform for all $1\leq t\leq{\hat{t}}$. Let $S_{n}$ be the set of all permutations on $\left[{n}\right]$. Let $\lambda_{\Phi}$ be the probability distribution on pairs $(\vec{\pi},\vec{\sigma})\in S_{n}\times\left\{{-1,1}\right\}^{V}$ induced by choosing a permutation $\vec{\pi}\in S_{n}$ uniformly at random and letting $\vec{\sigma}={\tt BPdec}(\Phi,\vec{\pi})$. Then $\bar{\beta}_{\Phi}$ is the $\vec{\sigma}$-marginal of $\lambda_{\Phi}$, i.e.,

In order to study $\lambda_{\Phi}$, we consider another distribution $\lambda_{\Phi}^{\prime}$ on pairs $(\vec{\pi},\vec{\sigma}^{\prime})\in S_{n}\times\left\{{0,1}\right\}^{V}$ that is easier to analyze and that will turn out to be ‘close’ to $\lambda_{\Phi}$. To define $\lambda_{\Phi}^{\prime}$, let $\mathcal{B}_{t}$ be the set of all pairs $(\pi,\sigma)$ such that $(\Phi,\pi,\sigma)$ is not $(\delta_{t},t)$-balanced. Moreover, let $\mathcal{B}=\bigcup_{t=0}^{T}\mathcal{B}_{t}$. The distribution $\lambda_{\Phi}^{\prime}$ is induced by choosing a permutation $\vec{\pi}$ uniformly at random and running the following algorithm on $\Phi,\vec{\pi}$.

BPdec${}^{\prime}(\Phi,\pi)$ Input: A $k$-SAT formula $\Phi$ on $V=\left\{{x_{1},\ldots,x_{n}}\right\}$ and a permutation $\pi\in S_{n}$. Output: An assignment $\vec{\sigma}^{\prime}:V\rightarrow\left\{{-1,1}\right\}$.

Roughly speaking, ${\tt BPdec}^{\prime}$ disregards the BP outcome if it strays too far from the ‘flat’ vector $\frac{1}{2}\vec{1}$. We claim that $\lambda_{\Phi}$ and $\lambda_{\Phi}^{\prime}$ are related as follows. For $\mathcal{F}\subset S_{n}\times\left\{{-1,1}\right\}^{V}$ let

Thus, $\mathcal{F}_{\hat{t}}$ is the set of all $(\pi,\sigma)$ that coincide with some $(\pi^{*},\sigma^{*})\in\mathcal{F}$ “up to time $\hat{t}$”. In particular, $\mathcal{F}\subset\mathcal{F}_{\hat{t}}$.

For any $\mathcal{F}\subset S_{n}\times\left\{{-1,1}\right\}^{V}$ we have $\lambda_{\Phi}(\mathcal{F})\leq\lambda_{\Phi}^{\prime}(\mathcal{F}_{\hat{t}})+\lambda_{\Phi}^{\prime}(\mathcal{B}).$

By construction, for any $(\pi,\sigma)\not\in\mathcal{B}_{t}$ and any $\zeta\in\left\{{-1,1}\right\}$ we have

Hence, Bayes’ rule yields that for any pair $(\pi,\sigma)\not\in\mathcal{B}$,

In particular, $\lambda_{\Phi}(\mathcal{B})=\lambda_{\Phi}^{\prime}(\mathcal{B})$. Hence, for any event $\mathcal{F}$ we obtain

Let $\lambda^{\prime\prime}$ be the uniform probability distribution on $S_{n}\times\left\{{-1,1}\right\}^{V}$, and let $(\vec{\pi},\vec{u})$ denote a pair chosen from $\lambda^{\prime\prime}$. To relate $\lambda_{\Phi}^{\prime}$ and $\lambda^{\prime\prime}$, let $A_{t}(\pi,\sigma)$ be equal to one if $(\pi,\sigma)\not\in\mathcal{B}_{t}$ and $x_{\pi(t)}$ is $(\delta_{t},t)$-biased in $(\Phi,\pi,\sigma)$, and set $A_{t}(\pi,\sigma)=0$ otherwise. In addition, let $A(\pi,\sigma)=\sum_{t\leq{\hat{t}}}A_{t}(\pi,\sigma)$.

For any pair $(\pi,\sigma)\in S_{n}\times\left\{{-1,1}\right\}^{V}$ we have

Fix any pair $(\pi,\sigma)\in S_{n}\times\left\{{-1,1}\right\}^{V}$ and let $\mathcal{L}_{t}$ be the event that

Then for any $1\leq t\leq{\hat{t}}$ we can bound the conditional probability $\lambda_{\Phi}^{\prime}\left[{\mathcal{L}_{t}|\vec{\pi}(t)=\pi(t)\wedge\bigwedge_{s<t}\mathcal{L}_{s}}\right]$ as follows.

In this case $(\Phi,\pi,\sigma)$ is not $(\delta_{t},t)$-balanced. Therefore, step 3 of BPdec’ chooses the value $\vec{\sigma}^{\prime}(x_{\pi(t)})$ uniformly. Hence, the event $\vec{\sigma}^{\prime}(x_{\pi(t)})=\sigma(x_{\pi(t)})$ occurs with probability $\frac{1}{2}$.

Since $(\Phi,\pi,\sigma)$ is $(\delta_{t},t)$-balanced, step 3 of BPdec’ uses the BP marginals $\mu_{x_{\pi(t)}}(\zeta)$ in order to assign $x_{\pi(t)}$. Because $A_{t}(\pi,\sigma)=0$, the variable $x_{\pi(t)}$ is not $(\delta_{t},t)$-biased, whence $\mu_{x_{\pi(t)}}(\zeta)\leq\frac{1}{2}+\delta_{t}$ for both $\zeta=-1$ and $\zeta=1$. Hence, the probability that $\vec{\sigma}^{\prime}(x_{\pi(t)})=\sigma(x_{\pi(t)})$ is bounded by $\frac{1}{2}+\delta_{t}$.

In this case we just use the trivial fact that the probability of the event $\vec{\sigma}^{\prime}(x_{\pi(t)})=\sigma(x_{\pi(t)})$ is bounded by $1\leq 2(\frac{1}{2}+\delta_{t})$.

In any case, we obtain the bound $\lambda_{\Phi}^{\prime}\left[{\mathcal{L}_{t}|\vec{\pi}(t)=\pi(t)\wedge\bigwedge_{s<t}\mathcal{L}_{s}}\right]\leq 2^{A_{t}(\pi,\sigma)}(\frac{1}{2}+\delta_{t})$. Consequently, as $\lambda^{\prime\prime}$ is the uniform distribution, we get

Multiplying (23) up for $t\leq{\hat{t}}$ yields the assertion. ∎

To put Lemma 6 to work, we need to estimate $A(\vec{\pi},\vec{\sigma}^{\prime})$.

We have $\lambda_{\Phi}^{\prime}\left[{A(\vec{\pi},\vec{\sigma}^{\prime})>4(\Delta_{\hat{t}}+\xi n)}\right]\leq\exp(-\xi n).$

We are going to bound the probability that $A_{t}(\vec{\pi},\vec{\sigma}^{\prime})=1$ given the values $\vec{\pi}(s)$, $\vec{\sigma}^{\prime}(x_{\vec{\pi}(s)})$ for $1\leq s<t$.

In this case $(\Phi,\pi,\sigma)$ is $(\delta_{t},t)$-balanced, which means that no more than $\delta_{t}(n-t)$ variables are biased. Since the permutation $\vec{\pi}$ is chosen uniformly at random, the probability that $x_{\vec{\pi}(t)}$ is $(\delta_{t},t)$-biased is bounded by $\delta_{t}$.

Thus, in either case the conditional probability of the event $A_{t}=1$ is bounded by $\delta_{t}$. This implies that the random variable $A(\vec{\pi},\vec{\sigma}^{\prime})=\sum_{t\leq{\hat{t}}}A_{t}(\vec{\pi},\vec{\sigma}^{\prime})$ is stochastically dominated by a sum of mutually independent Bernoulli variables with means $\delta_{1},\ldots,\delta_{\hat{t}}$. Therefore, the assertion follows from Lemma 2 (the Chernoff bound). ∎

Proof of Proposition 1. Combining Lemmas 6 and 7, we see that

Our assumption that $\Phi$ is $(t,\xi)$-uniform ensures that $\lambda^{\prime\prime}\left[{\mathcal{B}_{t}}\right]\leq\exp(-10(\xi n+\Delta_{\hat{t}}))$ for any $t\leq{\hat{t}}$. Together with (24), this implies that

Finally, consider any ${\cal E}\subset\left\{{-1,1}\right\}^{V}$. Let $\mathcal{F}=S_{n}\times{\cal E}$. Then

Tracing the Belief Propagation operator

Fix any permutation $\pi$ of $\left[{n}\right]$ and any assignment $\sigma\in\left\{{0,1}\right\}^{V}$. Then for any $0\leq t\leq\hat{t}$ we have

For a $k$-CNF $\Phi$ let $\Phi^{\pi,\sigma}$ be the formula obtained by replacing

each occurrence of the literal $x_{i}$ in $\Phi$ by $x_{\pi(i)}$ if $\sigma(x_{\pi(i)})=1$, and by $\neg x_{\pi(i)}$ if $\sigma(x_{\pi(i)})=-1$, and

each occurrence of the literal $\neg x_{i}$ in $\Phi$ by $\neg x_{\pi(i)}$ if $\sigma(x_{\pi(i)})=1$, and by $x_{\pi(i)}$ if $\sigma(x_{\pi(i)})=-1$.

the fraction of unassigned variables. Then our induction hypothesis is that for all but $\delta_{t}\theta n$ variables we have

Assume, furthermore, that $a$ is “not too short” – say, $|N(a)|\geq 0.1\theta k$. Then $2^{1-|N(a)|}\leq 2^{1-0.1\theta k}$ is small, and thus the expression in (32) is close to $1$. Hence, we can approximate it by

Thus, we need to show that for all but $\delta\theta n$ variables $x$ the exponent is close to zero.

we find that the expected number of clauses of length $j$ where $x\in V_{t}$ appears is asymptotically equal to

Indeed, the expected number of clauses of $\vec{\Phi}$ that $x$ appears in equals $km/n=kr=2^{k}\rho$. Furthermore, each of these gives rise to a clause of length $j$ in $\vec{\Phi}^{t}$ iff exactly $j-1$ among the other $k-1$ variables in the clause are from $V_{t}$, while the $k-j$ remaining variables are in $V\setminus V_{t}$ and occur with negative signs. (If one of them had a positive sign, the clause would have been satisfied by setting the corresponding variable to true. It would thus not be present in $\vec{\Phi}^{t}$ anymore.) Since $x$ appears with a random sign in each of these clauses, the sum

can be viewed as a random walk with an expected length of $\rho 2^{j}$. Thus, we expect an outcome of $O(\sqrt{2^{j}\rho})$. In this case, we find that

Together with the Chernoff bound, (36) shows that $x$ is unlikely to occur in clauses of lengths less than $0.1\theta k$ or more than $10\theta k$. Furthermore, our assumption that $\theta k\geq\ln(\rho)/c^{2}$ implies that $\sqrt{\rho}2^{-j/2}\leq\exp(-0.01\theta k)$ for all $j\geq 0.1\theta k$. Hence, we expect that for all but, say, $\delta_{t}\theta n/2$ variables $x\in V_{t}$

with $x\rightarrow a$, $y\rightarrow b$ ranging over all edges of the factor graph of $\vec{\Phi}^{t}$.

Since $\Lambda^{*}$ is based on $\vec{\Phi}^{t}$, it is a random matrix. One could therefore try to use standard arguments to bound it in some norm (say, $\left\|{\Lambda^{*}}\right\|_{\squareforqed}$). The problem with this approach is that $\Lambda^{*}$ is very high-dimensional: it operates on a space whose dimension is equal to the number of edges of the factor graph. In effect, standard random matrix arguments do not apply.

To resolve this problem, consider a “projection” of $\Lambda^{*}$ onto a space of dimension merely $|V_{t}|=\theta n$, namely

One can think of $\Lambda$ as a signed and weighted adjacency matrix of $\vec{\Phi}^{t}$. Standard arguments easily show that $\left\|{\Lambda}\right\|_{\squareforqed}\leq\delta_{t}^{4}\theta n$ is small with a very high probability. In effect, we expect that for all but, say, $\delta_{t}\theta n/2$ variables $x\in V_{t}$ we have

Rigorizing the sketch.

While the above outlines a strategy for tracing the BP operator, we clearly glossed over numerous issues. The rest of the paper is devoted to rectifying them. To provide a bit of orientation, let us briefly highlight the most important items, and indicate how they are going to be fixed.

The first issue is that Theorem 2.2 claims a rather strong bound on the probability that $\vec{\Phi}^{t}$ is $(\delta_{t},t)$-balanced. To obtain this bound, we are going to proceed in two steps: in Section 3.2 we will exhibit a small number quasirandom properties and show that these hold in $\vec{\Phi}^{t}$ with the required probability. Then, in Section 3.3 we are going to show deterministically that any formula that has these properties is $(\delta_{t},t)$-balanced.

To study the impact of the exceptional set, we decompose (31) as

Let us now turn this sketch into an actual proof. In Section 3.2 we introduce the quasirandomness property and state the deterministic result about BP on quasirandom formulas (Theorem 3.2). Then, from Section 3.3 onwards, we prove Theorem 3.2. Finally, in Section 4 we establish that the quasirandomness property holds on $\vec{\Phi}^{t}$ with the required probability.

2 The quasirandomness property

In this section we will exhibit a few simple quasirandomness properties that $\vec{\Phi}^{t}$ is very likely to possess. From Section 3.3 on we will show that these properties suffice to trace the BP operator.

For a variable $x\in V_{t}$ and a set $T\subset V_{t}$ let

Thus, $N_{\leq 1}(x,T)$ is the set of all clauses that contain $x$ (which may or may not be in $T$) and at most one other variable from $T$. In addition, there is a condition on the length $|N(b)|$ of the clause $b$ in the decimated formula $\Phi_{t}$. Recall from Section 3.1 that having assigned the first $t$ variables, we should ‘expect’ the average clause length to be $\theta k$.

Moreover, for a variable $x\in V_{t}$ and a set $T\subset V_{t}$ let

Let $\delta>0$. We say that $\Phi$ is ($\delta,t)$-quasirandom if Q0–Q4 in Figure 1 are satisfied.

Condition Q0 simply bounds the number of redundant clauses and the number of variables of very high degree; it well-known to hold for random $k$-CNFs w.h.p. Apart from a bound on the number of very short/very long clauses, Q1 provides a bound on the ‘weight’ of clauses in which variables $x\in V_{t}$ typically occur, where the weight of a clause $b$ is $2^{-|N(b)|}$. Moreover, Q2 provides that there is no small set $T$ for which the total weight of the clauses touching that set is very big. In addition, Q2 (essentially) requires that for most variables $x$ the weights of the clauses where $x$ occurs positively/negatively should approximately cancel. Further, Q3 provides a bound on the lengths of clauses that contain many variables from a small set $T$. Finally, the most important condition is Q4, providing a bound on the cut norm of a signed, weighted matrix representation of $\Phi^{t}$.

There exists a constant $\rho_{0}>0$ such that for any $k,r$ satisfying $\rho_{0}\cdot 2^{k}/k\leq r\leq 2^{k}\ln 2$ there is $\xi=\xi(k,r)>0$ so that for $n$ large and $\delta_{t}$, $\hat{t}$ as in (13) for any $1\leq t\leq\hat{t}$ we have

The proof of Proposition 2 is a necessary evil: it is long, complicated and based on standard arguments. We defer it to Section 4. Together with the following theorem, which we will establish in Section 3.3, Proposition 2 yields Theorem 2.2.

The rest of this section deals with the proof of Theorem 3.2.

For the rest of Section 3, we keep the notation from Section 3.2 and the assumptions of Theorem 3.2. To unclutter the notation, we let $\delta=\delta_{t}$.

3 Belief Propagation on quasirandom formulas: proof of Theorem 3.2

Implementing the strategy outlined in Section 3.1, we are going to trace the BP operator when iterated from the initial point

We have $\delta(\theta k)^{3}\sum_{b\in N(x)}2^{-|N(b)|}\leq 1$, and $0.1\theta k\leq|N(b)|\leq 10\theta k$ for all $b\in N(x)$.

Finally, in Section 3.8 we will derive Theorem 3.2 from Proposition 3 and Proposition 4.

4 Proof of Proposition 3

Furthermore, if $2^{2-|N(b)|+t_{b}}\exp(\delta|N(b)|)|\leq 1/2$, then

The second assertion follows from the elementary inequality $1-z\geq\exp(-2z)$ for $0\leq z\leq 1/2$. ∎

Our assumptions $t_{b}<|N(b)|-2$ and $|N(b)|\leq 10\theta k$ ensure that

whence $2^{2-|N(b)|+t_{b}}\exp(\delta|N(b)|)\leq 0.6$. Due to the elementary inequality $1-z\geq\exp(-2z)$ for $z\in\left[{0,0.6}\right]$, (45) thus yields

Multiplying (46) up over $b\in\mathcal{T}$ and taking logarithms yields

Since (47) holds for both $\zeta=-1$ and $\zeta=1$, the assertion follows. ∎

Moreover, H2 ensures that $\sum_{b\in\mathcal{T}}2^{t_{b}-|N(b)|}\leq\delta$, whence (48) entails

With respect to the second product, Corollary 3 yields

Furthermore, for any $b\in\mathcal{N}$ we have

Since $|N(b)|\geq 0.1k\theta$ by H1, (52) thus yields

Using the elementary inequality $-z-z^{2}\leq\ln(1-z)\leq-z$ for $0\leq z\leq 0.5$, we obtain from (52), (53) and (54)

Summing these bounds up for $b\in\mathcal{N}$, we obtain

Thus, we have established the assertion in either case. ∎

To establish (58), we consider two cases.

Thus, we have established (58) in either case.

5 Proof of Proposition 4

to conclude that the number of variables satisfying T2c is $\leq 0.001\theta\delta n$ as well.

Hence, there are at most $\nu\leq 0.01\theta\delta n$ variables that satisfy T2d. In summary, we have shown that

To deal with T2e, observe that if a clause $a$ has at least $|N(a)|/4$ variables that are not harmless, then one of the following statements is true.

$a$ contains at least $|N(a)|/20$ variables $x$ that violate either H1, H2, or H4.

$a$ contains at least $|N(a)|/5$ variables $x$ that violate condition H3.

Let ${\mathcal{C}}_{1}$ be the set of clauses $a$ for which i. holds, and let ${\mathcal{C}}_{2}$ be the set of clauses satisfying ii., so that the number of variables satisfying T2e is bounded by $\sum_{a\in{\mathcal{C}}_{1}\cup{\mathcal{C}}_{2}}|N(a)|$.

In addition, let $\mathcal{B}^{\prime\prime}$ be the set of all clauses of length less than $100k_{1}$. Since $100k_{1}=100\sqrt{c}\theta k\leq 0.1\theta k$ by our choice of $c$, Q1 implies that $|N(\mathcal{B}^{\prime\prime})|\leq 10^{-4}\delta\theta n$. Hence, (65) shows that $\mathcal{B}=\mathcal{B}^{\prime}\cup\mathcal{B}^{\prime\prime}$ satisfies

Furthermore, let $\mathcal{U}$ be the set of all clauses $a$ such that $N(a)\subset N(\mathcal{B})$. Let $U$ be the set of variables $x\in N(\mathcal{B})$ that occur in at least two clauses from $\mathcal{U}$. Then by Q3