Abstract 1 Introduction and results 2 Overview 3 Discussion References

Belief Propagation Guided Decimation on Random k-XORSAT

Arnab Chatterjee Faculty of Computer Science, TU Dortmund, Germany Amin Coja-Oghlan ORCID Faculty of Computer Science, TU Dortmund, Germany Mihyun Kang ORCID Institute of Discrete Mathematics, TU Graz, Austria Lena Krieg111corresponding author Faculty of Computer Science, TU Dortmund, Germany Maurice Rolvien Department of Informatics, University of Hamburg, Germany Gregory B. Sorkin Department of Mathematics, The London School of Economics and Political Science, UK
Abstract

We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random k-XORSAT problem. Specifically, we derive an explicit threshold up to which the algorithm succeeds with a strictly positive probability Ω(1) that we compute explicitly, but beyond which the algorithm with high probability fails to find a satisfying assignment. In addition, we analyse a thought experiment called the decimation process for which we identify a (non-) reconstruction and a condensation phase transition. The main results of the present work confirm physics predictions from [Ricci-Tersenghi and Semerjian: J. Stat. Mech. 2009] that link the phase transitions of the decimation process with the performance of the algorithm, and improve over partial results from a recent article [Yung: Proc. ICALP 2024].

Keywords and phrases:
random k-XORSAT, belief propagation, decimation process, random matrices
Category:
Track A: Algorithms, Complexity and Games
Funding:
Amin Coja-Oghlan: supported by DFG CO 646/3, DFG CO 646/5 and DFG CO 646/6.
Mihyun Kang: supported by Austrian Science Fund (FWF) 10.55776/I6502.
Lena Krieg: supported by DFG CO 646/3.
Maurice Rolvien: supported by DFG Research Group ADYN (FOR 2975) under grant DFG 411362735.
Copyright and License:
[Uncaptioned image] © Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien,
and Gregory B. Sorkin; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Probability and statistics
; Mathematics of computing Combinatoric problems ; Mathematics of computing Combinatorics ; Mathematics of computing Probabilistic algorithms
Related Version:
Full Version: https://arxiv.org/abs/2501.17657
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction and results

1.1 Background and motivation

The random k-XORSAT problem shares many characteristics of other intensely studied random constraint satisfaction problems (“CSPs”) such as random k-SAT. For instance, as the clause/variable density increases, random k-XORSAT possesses a sharp satisfiability threshold preceded by a reconstruction or “shattering” phase transition that affects the geometry of the set of solutions [2, 11, 16, 23]. As in random k-SAT, these transitions appear to significantly impact the performance of certain classes of algorithms [6, 15]. At the same time, random k-XORSAT is more amenable to mathematical analysis than, say, random k-SAT. This is because the XOR operation is equivalent to addition modulo two, which is why a k-XORSAT instance translates into a linear system over 𝔽2. In effect, k-XORSAT can be solved in polynomial time by means of Gaussian elimination. In addition, the algebraic nature of the problem induces strong symmetry properties that simplify its study [3].

Because of its similarities with other random CSPs combined with said relative amenability, random k-XORSAT provides an instructive benchmark. This was noticed not only in computer science, but also in the statistical physics community, which has been contributing intriguing “predictions” on random CSPs since the early 2000s [18, 21]. Among other things, physicists have proposed a message passing algorithm called Belief Propagation Guided Decimation (“𝙱𝙿𝙶𝙳”) that, according to computer experiments, performs impressively on various random CSPs [20]. Furthermore, Ricci-Tersenghi and Semerjian [24] put forward a heuristic analysis of 𝙱𝙿𝙶𝙳 on random k-SAT and k-XORSAT. Their heuristic analysis proceeds by way of a thought experiment based on an idealized version of the algorithm. We call this thought experiment the decimation process. Based on physics methods Ricci-Tersenghi and Semerjian surmise that the decimation process undergoes two phase transitions, specifically a reconstruction and a condensation transition. A key prediction of Ricci-Tersenghi and Semerjian is that these phase transitions are directly linked to the performance of the 𝙱𝙿𝙶𝙳 algorithm. Due to the linear algebra-induced symmetry properties, in the case of random k-XORSAT all of these conjectures come as elegant analytical expressions.

The aim of this paper is to verify the predictions from [24] on random k-XORSAT mathematically. Specifically, our aim is to rigorously analyse the 𝙱𝙿𝙶𝙳 algorithm on random k-XORSAT, and to establish the link between its performance and the phase transitions of the decimation process. A first step towards a rigorous analysis of 𝙱𝙿𝙶𝙳 on random k-XORSAT was undertaken in a recent contribution by Yung [25]. However, Yung’s analysis turns out to be not tight. Specifically, apart from requiring spurious lower bounds on the clause length k, Yung’s results do not quite establish the precise connection between the decimation process and the performance of 𝙱𝙿𝙶𝙳. One reason for this is that [25] relies on “annealed” techniques, i.e., essentially moment computations. Here we instead harness “quenched” arguments that were partly developed in prior work on the rank of random matrices over finite fields [3, 8].

Throughout we let k3 and nk be integers and d>0 a positive real. Let 𝒎=distPo(dn/k) and let 𝑭=𝑭(n,d,k) be a random k-XORSAT formula 333 Two random variables 𝑿,𝒀 are equal in distribution 𝑿=dist𝒀 if they have the same distribution functions. Here, 𝒎 follows a Poisson distribution with mean dn/k. with variables x1,,xn and 𝒎 random clauses of length k. To be precise, every clause of 𝑭 is an XOR of precisely k distinct variables, each of which may or may not come with a negation sign. The 𝒎 clauses are drawn uniformly and independently out of the set of all 2k(nk) possibilities. Thus, d equals the average number of clauses that a given variable xi appears in.

1.2 Belief Propagation Guided Decimation

The first result vindicates the predictions from [24] concerning the success probability of 𝙱𝙿𝙶𝙳 algorithm. 𝙱𝙿𝙶𝙳 sets its ambitions higher than merely finding a solution to the k-XORSAT instance 𝑭: the algorithm attempts to sample a solution uniformly at random. To this end 𝙱𝙿𝙶𝙳 assigns values to the variables x1,,xn of 𝑭 one after the other. In order to assign the next variable the algorithm attempts to compute the marginal probability that the variable is set to “true” under a random solution to the k-XORSAT instance, given all previous assignments. More precisely, suppose 𝙱𝙿𝙶𝙳 has assigned values to the variables x1,,xt already. Write 𝝈BP(x1),,𝝈BP(xt){0,1} for their values, with 1 representing “true” and 0 “false”. Further, let 𝑭BP,t be the simplified formula obtained by substituting 𝝈BP(x1),,𝝈BP(xt) for x1,,xt. We drop any clauses from 𝑭BP,t that contain variables from {x1,,xt} only, deeming any such clauses satisfied. Thus, 𝑭BP,t is a XORSAT formula with variables xt+1,,xn. Its clauses contain at least one and at most k variables, as well as possibly a constant (the XOR of the values substituted in for x1,,xt).

Let 𝝈𝑭BP,t be a uniformly random solution of the XORSAT formula 𝑭BP,t, assuming that 𝑭BP,t remains satisfiable. Then 𝙱𝙿𝙶𝙳 aims to compute the marginal probability [𝝈𝑭BP,t(xt+1)=1𝑭BP,t] that a random satisfying assignment of 𝑭BP,t sets xt+1 to true. This is where Belief Propagation (“BP”) comes in. An efficient message passing heuristic for computing precisely such marginals, BP returns an “approximation” μ𝑭BP,t of [𝝈𝑭BP,t(xt+1)=1𝑭BP,t]. We will recap the mechanics of BP in Section 2.2 (the value μ𝑭BP,t is defined precisely in (2.9)). Having computed the BP “approximation”, 𝙱𝙿𝙶𝙳 proceeds to assign xt+1 the value “true” with probability μ𝑭BP,t, otherwise sets xt+1 to “false”, then moves on to the next variable. The pseudocode is displayed as Algorithm 1.

Algorithm 1 The 𝙱𝙿𝙶𝙳 algorithm.

Let us pause for a few remarks. First, if the BP approximations are exact, i.e., if 𝑭BP,t is satisfiable and μ𝑭BP,t=[𝝈𝑭BP,t(xt+1)=1𝑭BP,t] for all t, then Bayes’ formula shows that 𝙱𝙿𝙶𝙳 outputs a uniformly random solution of 𝑭. However, there is no universal guarantee that BP returns the correct marginals. Accordingly, the crux of analysing 𝙱𝙿𝙶𝙳 is precisely to figure out whether this is the case. Indeed, the heuristic work of [24] ties the accuracy of BP to a phase transition of the decimation process thought experiment, to be reviewed momentarily.

Second, the strategy behind the 𝙱𝙿𝙶𝙳 algorithm, particularly the message passing heuristic for “approximating” the marginals, generalizes well beyond k-XORSAT. For instance, the approach applies to k-SAT verbatim. That said, due to the algebraic nature of the XOR operation, 𝙱𝙿𝙶𝙳 is far easier to analyse on k-XORSAT. In fact, in XORSAT the marginal probabilities are guaranteed to be half-integral as seen in Fact 2.2, i.e.,

[𝝈𝑭BP,t(xt+1)=1𝑭BP,t]{0,1/2,1}. (1.1)

As a consequence, on XORSAT the 𝙱𝙿𝙶𝙳 algorithm effectively reduces to a purely combinatorial algorithm called Unit Clause Propagation [18, 24] as per Proposition 11, a fact that we will exploit extensively (see Section 2.7).

1.3 A tight analysis of 𝙱𝙿𝙶𝙳

In order to state the main results we need to introduce a few threshold values. To this end, given d,k and an additional real parameter λ0 that depends on the time t, consider the functions 444The function Φd,k,λ is known in physics parlance as the “Bethe free entropy” [8, 18]. The stationary points of Φd,k,λ coincide with the fixed points of ϕd,k,λ, as we will verify in Section 2.1.

ϕd,k,λ: [0,1][0,1], z 1exp(λdzk1), (1.2)
Φd,k,λ: [0,1], z exp(λdzk1)d(k1)kzk+dzk1dk. (1.3)

Let α(λ)=α(d,k,λ)[0,1] be the smallest and α(λ)=α(d,k,λ)α(d,k,λ)[0,1] the largest fixed point of ϕd,k,λ. Figure 2 visualizes Φ(z) for different values of θt/n. Further, define

dmin(k) =(k1k2)k2,dcore(k)=sup{d>0:α(0)=0}, (1.4)
dsat(k) =sup{d>0:Φd,k,0(α(0))Φd,k,0(0)}. (1.5)

The value dsat(k) is the random k-XORSAT satisfiability threshold [3, 11, 23]. Thus, for d<dsat(k) the random k-XORSAT formula 𝑭 possesses satisfying assignments w.h.p., while 𝑭 is unsatisfiable for d>dsat(k) w.h.p. Furthermore, dcore(k) equals the threshold for the emergence of a giant 2-core within the k-uniform hypergraph induced by 𝑭 [3, 22]. This implies that for d<dcore(k) the set of solutions of 𝑭 is connected in a certain well-defined way, while for dcore(k)<d<dsat(k) the set of solutions shatters into an exponential number of well-separated clusters [15, 18]. Moreover, a simple linear time algorithm is known to find a solution w.h.p. for d<dcore(k) [15]. The relevance of dmin(k) will emerge in Theorem 1. A bit of calculus reveals that

0<dmin(k)<dcore(k)<dsat(k)<k. (1.6)

The following theorem determines the precise clause-to-variable densities where 𝙱𝙿𝙶𝙳 succeeds/fails. To be precise, in the “successful” regime 𝙱𝙿𝙶𝙳 does not actually succeed with high probability, but with an explicit probability strictly between zero and one, which is displayed in Figure 2 for k=3,4,5.

Figure 1: Φd,k,λ for k=3 and d=2.4, for λ from 0 to 0.3 (maximum at z=0) and from 0.4 to 0.9.
Figure 2: Success probability of 𝙱𝙿𝙶𝙳 for 0<d<dmin(k) and various k.
 
Theorem 1.

Let k3.

  1. (i)

    If d<dmin(k), then

    limn[𝙱𝙿𝙶𝙳(𝑭) succeeds] =exp(d2(k1)2401z2k4(1z)1d(k1)zk2(1z)dz). (1.7)
  2. (ii)

    If dmin(k)<d<dsat(k), then [𝙱𝙿𝙶𝙳(𝑭) succeeds]=o(1).

Theorem 1 vindicates the predictions from Ricci-Tersenghi and Semerjian [24, Section 4] as to the performance of 𝙱𝙿𝙶𝙳, and improves over the results from Yung [25]. Specifically, Theorem 1 (i) verifies the formula for the success probability from [24, Eq. (38)]. Combinatorially, the formula (1.7) results from the possible presence of bounded length cycles (so called toxic cycles) that may cause the algorithm to run into contradictions. This complements Yung’s prior work, that has no positive result on the performance of 𝙱𝙿𝙶𝙳. Moreover, Yung’s negative results [25, Theorems 2–3] only apply to k9 and to d>dcore(k), while Theorem 1 (ii) covers all k3 and kicks in at the correct threshold dmin(k)<dcore(k) predicted in [24].

1.4 The decimation process

In addition to the 𝙱𝙿𝙶𝙳 algorithm itself, the heuristic work [24] considers an idealised version of the algorithm, the decimation process. This thought experiment highlights the conceptual reasons behind the success/failure of 𝙱𝙿𝙶𝙳. Just like 𝙱𝙿𝙶𝙳, the decimation process assigns values to variables one after the other for good. But instead of the BP “approximations” the decimation process uses the actual marginals given its previous decisions. To be precise, suppose that the input formula 𝑭 is satisfiable and that variables x1,,xt have already been assigned values 𝝈DC(x1),,𝝈DC(xt) in the previous iterations. Obtain 𝑭DC,t by substituting the values 𝝈DC(x1),,𝝈DC(xt) for x1,,xt and dropping any clauses that do not contain any of xt+1,,xn. Thus, 𝑭DC,t is a XORSAT formula with variables xt+1,,xn. Let 𝝈𝑭DC,t be a random satisfying assignment of 𝑭DC,t. Then the decimation process sets xt+1 according to the true marginal [𝝈𝑭DC,t(xt+1)=1𝑭DC,t], thus ultimately returning a uniformly random satisfying assignment of 𝑭.

Algorithm 2 The decimation process.

Clearly, if indeed the BP “approximations” are correct, then the decimation process and 𝙱𝙿𝙶𝙳 are identical. Thus, a key question is for what parameter regimes the two process coincide or diverge, respectively. As it turns out, this question is best answered by parametrise not only in terms of the average variable degree d, but also in terms of the “time” parameter t of the decimation process.

1.5 Phase transitions of the decimation process

Ricci-Tersenghi and Semerjian heuristically identify several phase transitions in terms of d and t that the decimation process undergoes. We will confirm these predictions mathematically and investigate how they relate to the performance of 𝙱𝙿𝙶𝙳.

The first set of relevant phase transitions concerns the so-called non-reconstruction property. Roughly speaking, non-reconstruction means that the marginal π𝑭DC,t=[𝝈𝑭DC,t(xt+1)=1𝑭DC,t] is determined by short-range rather than long-range effects. Since Belief Propagation is essentially a local algorithm, one might expect that the (non-)reconstruction phase transition coincides with the threshold up to which 𝙱𝙿𝙶𝙳 succeeds; cf. the discussions in [5, 16].

To define (non-)reconstruction precisely, we associate a bipartite graph G(𝑭DC,t) with the formula 𝑭DC,t. The vertices of this graph are the variables and clauses of 𝑭DC,t. Each variable is adjacent to the clauses in which it appears. For a (variable or clause) vertex v of G(𝑭DC,t) let v be the set of neighbours of v in G(𝑭DC,t).More generally, for an integer 1 let v be the set of vertices of G(𝑭DC,t) at shortest path distance precisely from v. Following [16], we say that 𝑭DC,t has the non-reconstruction property if

limlim supn𝔼[|[𝝈𝑭DC,t(xt+1)=1|𝑭DC,t,{𝝈𝑭DC,t(y)}y2xt+1] (1.8)
[𝝈𝑭DC,t(xt+1)=1𝑭DC,t]||𝑭 satisfiable] =0.

Conversely, 𝑭DC,t has the reconstruction property if

lim inflim infn𝔼[|[𝝈𝑭DC,t(xt+1)=1|𝑭DC,t,{𝝈𝑭DC,t(y)}y2xt+1] (1.9)
[𝝈𝑭DC,t(xt+1)=1𝑭DC,t]||𝑭 sat.] >0.

To parse (1.8), notice that in the left probability term we condition on both the outcome 𝑭DC,t of the first t steps of the decimation process and on the values 𝝈𝑭DC,t(y) that the random solution 𝝈𝑭DC,t assigns to the variables y at distance exactly 2 from xt+1. By contrast, in the right probability term we only condition on 𝑭DC,t. Thus, the second probability term matches the probability π𝑭DC,t from the decimation process. Hence, (1.8) compares the probability that a random solution sets xt+1 to one given the values 𝝈𝑭DC,t(y) of all variables y at distance 2 from xt+1 with plain marginal probability that xt+1 is set to one. What (1.8) asks is that these two probabilities be asymptotically equal in the limit of large , with high probability over the choice of 𝑭 and the prior steps of the decimation process.

Confirming the predictions from [24], the following theorem identifies the precise regimes of d,t where (non-)reconstruction holds. To state the theorem, we need to know that for dmin(k)<d<dsat(k) the polynomial d(k1)zk2(1z)1 has precisely two roots 0<z=z(d,k)<z=z(d,k)<1; we are going to prove this as part of Proposition 4 below. Let

λ =λ(d,k)=log(1z)z(k1)(1z) (1.10)
>λ=λ(d,k)=max{0,log(1z)z(k1)(1z)}0, (1.11)
θ =θ(d,k)=1exp(λ)>θ=θ(d,k)=1exp(λ). (1.12)

Additionally, let λcond(d,k) be the solution to the ODE

λcond(d,k)d =α(λcond(d,k))kα(λcond(d,k))kk(α(λcond(d,k))α(λcond(d,k))), λcond(dsat(k),k) =0 (1.13)

on (dmin,dsat] and set θcond=θcond(d,k)=1exp(λcond(d,k)). Note that θ<θcond<θ.

Theorem 2.

Let k3 and let 0t=t(n)n be a sequence such that limnt/n=θ(0,1).

  1. (i)

    If d<dmin(k), then 𝑭DC,t has the non-reconstruction property w.h.p.

  2. (ii)

    If dmin(k)<d<dsat(k) and θ<θ or θ>θcond, then 𝑭DC,t has the non-reconstruction property w.h.p.

  3. (iii)

    If dmin(k)<d<dsat(k) and θ<θ<θcond, then 𝑭DC,t has the reconstruction property w.h.p.

Theorem 2 shows that dmin(k) marks the precise threshold of d up to which the decimation process 𝑭DC,t exhibits non-reconstruction for all 0tn w.h.p. By contrast, for dmin(k)<d<dsat(k) there is a regime of t where reconstruction occurs. In fact, as Proposition 4 shows, for d>dcore(k) we have θ=0 and thus reconstruction holds even at t=0, i.e., for the original, undecimated random formula 𝑭. Prior to the contribution [24], it had been suggested that this precise scenario (reconstruction on the original problem instance) is the stone on which 𝙱𝙿𝙶𝙳 stumbles [5]. In fact, Yung’s negative result kicks in at this precise threshold dcore(k). However, Theorems 1 and 2 show that matters are more subtle. Specifically, for dmin(k)<d<dcore(k) reconstruction, even though absent in the initial formula 𝑭, occurs at a later “time” t>0 as decimation proceeds, which suffices to trip 𝙱𝙿𝙶𝙳 up. Also, remarkably, Theorem 2 shows that non-reconstruction is not “monotone”. The property holds for θ<θ and then again for θ>θcond, but not on the interval (θ,θcond) as visualised in Figure 3.

But there is one more surprise. Namely, Theorem 2 (ii) might suggest that for dmin(k)<d<dsat(k) Belief Propagation manages to compute the correct marginals for t/nθ>θcond, as non-reconstruction kicks back in. But remarkably, this is not quite true. Despite the fact that non-reconstruction holds, 𝙱𝙿𝙶𝙳 goes astray because the algorithm starts its message passing process from a mistaken, oblivious initialisation. As a consequence, for t/nθ(θcond,θ) the BP “approximations” remain prone to error. To be precise, the following result identifies the precise “times” where BP succeeds/fails. To state the result let μ𝑭DC,t denote the BP “approximation” of the true marginal π𝑭DC,t of variable xt+1 in the formula 𝑭DC,t created by the decimation process (see Section 2.2 for a reminder of the definition). Also recall that π𝑭DC,t denotes the correct marginal as used by the decimation process.

Theorem 3.

Let k3 and let 0t=t(n)n be a sequence such that limnt/n=θ(0,1).

  1. (i)

    If 0<d<dmin(k) then μ𝑭DC,t=π𝑭DC,t w.h.p.

  2. (ii)

    If dmin(k)<d<dsat(k) and θ<θcond or θ>θ, then μ𝑭DC,t=π𝑭DC,t w.h.p.

  3. (iii)

    If dmin(k)<d<dsat(k) and θcond<θ<θ, then 𝔼|μ𝑭DC,tπ𝑭DC,t|=Ω(1).

The upshot of Theorems 23 is that the relation between the accuracy of BP and reconstruction is subtle. Everything goes well so long as d<dmin as non-reconstruction holds throughout and the BP approximations are correct. But if dmin<d<dsat and θ<θ<θcond, then Theorem 2 (iii) shows that reconstruction occurs. Nonetheless, Theorem 3 (ii) demonstrates that the BP approximations remain valid in this regime. By contrast, for θcond<θ<θ we have non-reconstruction by Theorem 2 (iii), but Theorem 3 (iii) shows that BP misses its mark with a non-vanishing probability. Finally, for θ>θ everything is in order once again as BP regains its footing and non-reconstruction holds. Unfortunately 𝙱𝙿𝙶𝙳 is unlikely to reach this happy state because the algorithm is bound to make numerous mistakes at times t/n(θcond,θ).

(a) k=3
(b) k=4
(c) k=5
Figure 3: The phase diagrams for k=3,4,5 with d(dmin,dsat) on the horizontal and θ on the vertical axis. The hatched area displays the regime θ<θ and θcond<θ where non reconstruction holds. In the non hatched area, where θ<θ<θcond, we have reconstruction. Similarly, the blue area displays θ<θcond and θ>θ where BP is correct whereas in the orange area, BP is inaccurate.

Theorems 2 and 3 confirm the predictions from [24, Section 4]. To be precise, while θcond matches the predictions of Ricci-Tersenghi and Semerjian, the ODE formula (1.13) for the threshold, which is easy to evaluate numerically, does not appear in [24]. Instead of the ODE formulation, Ricci-Tersenghi and Semerjian define λcond as the (unique) λ0 such that Φd,k,λ(α)=Φd,k,λ(α); Proposition 4 below shows that both are equivalent. Illustrating Theorems 23, Figure 3 displays the phase diagram in terms of d and θt/n for k=3,4,5.

2 Overview

This section provides an overview of the proofs of Theorems 13. In the final paragraph we conclude with a discussion of further related work. We assume throughout that k3 is an integer and that 0<d<dsat(k). Moreover, t=t(n) denotes an integer sequence 0t(n)n such that limnt(n)/n=θ(0,1).

2.1 Fixed points and thresholds

The first item on our agenda is to study the functions ϕd,k,λ,Φd,k,λ from (1.2)–(1.3). Specifically, we are concerned with the maxima of Φd,k,λ and the fixed points of ϕd,k,λ, the combinatorial relevance of which will emerge as we analyse 𝙱𝙿𝙶𝙳 and the decimation process. We begin by observing that the fixed points of ϕd,k,λ are precisely the stationary points of Φd,k,λ.

Fact 3.

For any d>0,λ0 the stationary points z(0,1) of Φd,k,λ coincide with the fixed points of ϕd,k,λ in (0,1). Furthermore, for a fixed point z(0,1) of ϕd,k,λ we have

Φd,k,λ′′(z) {<0 if ϕd,k,λ(z)<1,=0 if ϕd,k,λ(z)=1,>0 if ϕd,k,λ(z)>1. (2.1)

We recall that 0α=α(d,k,λ)α=α(d,k,λ)1 are the smallest and the largest fixed point of ϕd,k,λ in [0,1], respectively. Fact 2.1 shows that Φd,k,λ attains its global maximum in [0,1] at α or α. Let αmax=αmax(d,k,λ){α,α} be the maximiser of Φd,k,λ; if Φd,k,λ(α)=Φd,k,λ(α), set αmax=α. An example for α,α,αmax and Φ(α),Φ(α),Φ(αmax) is visualised in Figure 4. The following proposition characterises the fixed points of ϕd,k,λ and the maximiser αmax.

Proposition 4.
  1. (i)

    If d<dmin(k), then for all λ>0 we have α=α, the function λ(0,)α(0,1) is analytic, and α is the unique stable fixed point of ϕd,k,λ.

  2. (ii)

    If dmin(k)<d<dsat(k), then the polynomial d(k1)zk2(1z)1 has precisely two roots 0<z<z<1, the numbers λ,λ from (1.10) satisfy 0λ<λ and the following is true.

    1. (a)

      If λ<λ or λ>λ, then α=α(0,1) is the unique stable fixed point of ϕd,k,λ.

    2. (b)

      If λ<λ<λ, then 0<α<α<1 are the only stable fixed points of ϕd,k,λ.

    3. (c)

      The functions λ(0,λ)α and λ(λ,)α are analytic.

    4. (d)

      If dmin(k)<d<dsat(k), then the solution λcond of (1.13) satisfies λ<λcond=λcond(d)<λ and αmax=α if λ<λcond while αmax=α if λ>λcond.

(a) αmax
(b) Φ(αmax)
Figure 4: αmax and Φ(αmax) for d=2.4 and k=3 from θ to θ.

2.2 Belief Propagation

Having done our analytic homework, we proceed to recall how Belief Propagation computes the “approximations” μ𝑭BP,t that the 𝙱𝙿𝙶𝙳 algorithm relies upon. We will see that due to the inherent symmetries of XORSAT the Belief Propagation computations simplify and boil down to a simpler message passing process called Warning Propagation. Subsequently we will explain the connection between Warning Propagation and the fixed points α,α of ϕd,k,λ.

It is probably easiest to explain BP on a general XORSAT instance F with a set V(F) of variables and a set C(F) of clauses of lengths between one and k. As in Section 1.5 we consider the graph G(F) induced by F, with vertex set V(F)C(F) and an edge xa between xV(F) and aC(F) iff a contains x. Let v=Fv be the set of neighbours of vV(F)C(F). Additionally, given an assignment τ{0,1}a of the variables that appear in a, we write τa iff τ satisfies a.

With each clause/variable pair x,a such that xa Belief Propagation associates two sequences of “messages” (μF,xa,)0, (μF,ax,)0 directed from x to a and from a to x, respectively. These messages are probability distributions on {0,1}, i.e.,

μF,xa,=(μF,xa,(0),μF,xa,(1)),μF,ax,=(μF,ax,(0),μF,ax,(1)), (2.2)
μF,xa,(0)+μF,xa,(1)=μF,ax,(0)+μF,ax,(1) =1. (2.3)

The initial messages are uniform, i.e.,

μF,xa,0(s)=μF,ax,0(s) =1/2 (s{0,1}). (2.4)

Further, the messages at step +1 are obtained from the messages at step via the Belief Propagation equations

μF,ax,+1(s) τ{0,1}a1{τx=s,τa}ya{x}μF,ya,(τy), (2.5)
μF,xa,+1(s) bx{a}μF,bx,(s). (2.6)

In (2.5)–(2.6) the -symbol represents the normalisation required to ensure that the updated messages satisfy (2.3). In the case of (2.6) such a normalization may be impossible because the expressions on the r.h.s. could vanish for both s=0 and s=1. In this event we agree that

μF,xa,+1(s)={μF,xa,(s) if μF,xa,(s)1/21{s=0} otherwise (s{0,1});

in other words, we retain the messages from the previous iteration unless its value was 1/2, in which case we set μF,xa,+1(0)=1. The same convention applies to μF,ax,+1(s). Further, at any time t the BP messages render a heuristic “approximation” of the marginal probability that a random solution to the formula F sets a variable x to s{0,1}:

μF,x,(s) bxμF,bx,(s). (2.7)

We set μF,x,(0)=1μF,x,(1)=1 if s{0,1}bxμF,bx,(s)=0.

Fact 4.

The BP messages and marginals are half-integral for all t, i.e., for all t0 and s{0,1} we have

μF,xa,(s),μF,ax,(s),μF,x,(s){0,1/2,1}. (2.8)

Furthermore, for all >2aC(F)|a| we have μF,x,(s)=μF,x,+1(s).

Finally, in light of Fact 2.2 it makes sense to define the approximations for 𝙱𝙿𝙶𝙳 by letting

μ𝑭BP,t =limμ𝑭BP,t,xt+1,(1), μ𝑭DC,t =limμ𝑭DC,t,xt+1,(1). (2.9)

2.3 Warning Propagation

Thanks to the half-integrality (2.8) of the messages, Belief Propagation is equivalent to a purely combinatorial message passing procedure called Warning Propagation (“WP”) [18]. Similar as BP, WP also associates two message sequences (ωF,xa,,ωF,ax,)0 with every adjacent clause/variable pair. The messages take one of three possible discrete values {𝚏,𝚞,𝚗} (“frozen”, “uniform”, “null”). Essentially, 𝚗 indicates that the value of a variable is determined by unit clause propagation. Moreover, 𝚏 indicates that a variable is forced to take the value 0 once all variables in the 2-core of the hypergraph representation of the formula are set to 0. The remaining label 𝚞 indicates that neither of the above applies. To trace the BP messages from Section 2.2 actually only the two values {𝚗,𝚞} would be necessary. However, the third value 𝚏 will prove useful in order to compare the BP approximations with the actual marginals. Perhaps unexpectedly given the all-uniform initialisation (2.4), we launch WP from all-frozen start values:

ωF,xa,0=ωF,ax,0=𝚏 for all a,x. (2.10)

Subsequently the messages get updated according to the rules

ωF,ax,+1 ={𝚗 if ωF,ya,=𝚗 for all ya{x},𝚏if ωF,ya,𝚞 for all ya{x} and ωF,ya,𝚗 for at least one ya{x},𝚞 otherwise, (2.11)
ωF,xa,+1 ={𝚗 if ωF,bx,=𝚗 for at least one bx{a},𝚏if ωF,bx,𝚗 for all bx{a} and ωF,bx,=𝚏 for at least one bx{a},𝚞 otherwise. (2.12)

In addition to the messages we also define the mark ωF,x, of variable node x as in (2.11), or be it without omitting clause a. The following statement summarises the relationship between BP and WP.

Fact 4.

For all t0 and all x,a we have

μxa,(1) =1/2 ωF,xa, 𝚗, (2.13)
μax,(1) =1/2 ωF,ax, 𝚗, (2.14)
μx,(1) =1/2 ωF,x, 𝚗. (2.15)

Moreover, for all >2|C(F)| we have ωF,xa,=ωF,xa,+1 and ωF,ax,=ωF,ax,+1.

Fact 2.3 implies that the WP messages and marks “converge” in the limit of large , in the sense that eventually they do not change any more. Let ωF,xa,ωF,ax,ωF,x{𝚏,𝚞,𝚗} be these limits. Furthermore, let V𝚏,(F), V𝚞,(F), V𝚗,(F) be the sets of variables with the respective mark after 0 iterations. Also let V𝚏(F),V𝚞(F),V𝚗(F) be the sets of variables where the limit ωF,x takes the respective value. The following statement traces WP on the random formula 𝑭DC,t produced by the decimation process.

Proposition 5.

Let ε>0 and assume that d>0, t=t(n)θn satisfy one of the following conditions:

  1. (i)

    d<dmin, or

  2. (ii)

    d>dmin and θ{θ,θ}.

Then there exists 0=0(d,θ,ε)>0 such that for any fixed 0 with λ=log(1θ) w.h.p. we have

|t+|V𝚗,(𝑭DC,t)|αn| <εn, |t+|V𝚏,(𝑭DC,t)|(αα)n| <εn, (2.16)
|V𝚗(𝑭DC,t)V𝚗,(𝑭DC,t)| <εn. (2.17)

2.4 The check matrix

Since the XOR operation is equivalent to addition modulo two, a XORSAT formula F with variables x1,,xn and clauses a1,,am translates into a linear system over 𝔽2, as follows. Let AF be the m×n-matrix over 𝔽2 whose (i,j)-entry equals one iff variable xj appears in clause ai. Adopting coding parlance, we refer to AF as the check matrix of F. Furthermore, let yF𝔽2m be the vector whose ith entry is one plus the sum of any constant term and the number of negation signs of clause ai mod two. Then the solutions σ𝔽nn of the linear system AFσ=yF are precisely the satisfying assignments of F.

The algebraic properties of AF therefore have a direct impact on the satisfiability of F. For example, if AF has rank m, we may conclude immediately that F is satisfiable. Furthermore, the set of solutions of F is an affine subspace of 𝔽2n (if non-empty). In effect, if F is satisfiable, then the number of satisfying assignments equals the size of the kernel of AF. Hence the nullity nulAF=dimkerAF of the check matrix is a key quantity.

Indeed, the single most significant ingredient towards turning the heuristic arguments from [24] into rigorous proofs is a formula for the nullity of the check matrix of the XORSAT instance 𝑭DC,t from the decimation process. To unclutter the notation set 𝑨t=A𝑭DC,t. We derive the following proposition from a recent general result about the nullity of random matrices over finite fields [8, Theorem 1.1]. The proposition clarifies the semantics of the function Φd,k,λ and its maximiser αmax. In physics jargon Φd,k,λ is known as the Bethe free entropy.

Proposition 6.

Let d>0 and λ=log(1θ). Then

limnnul𝑨t =Φd,k,λ(αmax) in probability.

2.5 Null variables

Proposition 6 enables us to derive crucial information about the set of satisfying assignments of 𝑭DC,t. Specifically, for any XORSAT instance F with variables x1,,xn let V0(F) be the set of variables xi such that σi=0 for all σkerAF. We call the variables xiV0(F) null variables. Since the set of solutions of F, if non-empty, is a translation of kerAF, any two solutions σ,σ of F set the variables in V0(F) to exactly the same values. The following proposition shows that WP identifies certain variables as null.

Proposition 7.

W.h.p. the following two statements are true for any fixed integer >0.

  1. (i)

    We have V𝚗,(𝑭DC,t)V0(𝑭DC,t).

  2. (ii)

    We have |V𝚞,(𝑭DC,t)V0(𝑭DC,t)|=o(n).

Propositions 6 and 7 enable us to calculate the number of null variables of 𝑭DC,t, so long as we remain clear of the point θcond where αmax is discontinuous.

Proposition 8.

If θθcond then |V0(𝐅DC,t)|=αmaxn+o(n) w.h.p.

Let us briefly summarise what we have learned thus far. First, because all Belief Propagation messages are half-integral, BP reduces to WP. Second, Proposition 5 shows that the fixed points α,α of ϕd,k,λ determine the number of variables marked 𝚗 or 𝚏 by WP. Third, the function Φd,k,λ and its maximiser αmax govern the nullity of the check matrix and thereby the number of null variables of 𝑭DC,t. Clearly, the null variables xi are precisely the ones whose actual marginals [𝝈𝑭DC,t(xi)=s𝑭DC,t] are not uniform. As a next step, we investigate whether BP/WP identify these variables correctly.

In light of Proposition 5, in order to investigate the accuracy of BP it suffices to compare the numbers of variables marked 𝚗 by WP with the true marginals. The following corollary summarises the result.

Corollary 9.

For any d, θ the following statements are true.

  1. (i)

    If d<dmin, or d>dmin and θ<θcond, or d>dmin and θ>θ, then

    |V0(𝑭DC,t)V𝚗(𝑭DC,t)|=o(n)w.h.p.
  2. (ii)

    If d>dmin and θcond<θ<θ, then |V0(𝑭DC,t)V𝚗(𝑭DC,t)|=Ω(n) w.h.p.

Thus, so long as d<dmin or d>dmin and θ<θcond or θ>θ, the BP/WP approximations are mostly correct. By contrast, if d>dmin and θcond<θ<θ, the BP/WP approximations are significantly at variance with the true marginals w.h.p. Specifically, w.h.p. BP deems Ω(n) frozen variables unfrozen, thereby setting itself up for failure. Indeed, Corollary 9 easily implies Theorem 3, which in turn implies Theorem 1 (ii) without much ado.

In addition, to settle the (non-)reconstruction thresholds set out in Theorem 2 we need to investigate the conditional marginals given the values of variables at a certain distances from xt+1 as in (1.8). This is where the extra value 𝚏 from the construction of WP enters. Indeed, for a XORSAT instance F with variables x1,,xn and an integer let V0,(F) be the set of variables xi such that σi=0 for all σkerAF and σh=0 for all variables xhxi. Hence, V0,(F)V0(F) is the set of variables whose -neighbourhood is contained in V0(F).

Corollary 10.

Assume that d>dmin and let ε>0.

  1. (i)

    If θ<θcond, then for any fixed we have |V𝚏,(𝑭DC,t)V0,(𝑭DC,t)|<εn w.h.p.

  2. (ii)

    If θ>θcond, then there exists 0=0(d,θ,ε) such that for any fixed >0 we have

    |(V𝚗,(𝑭DC,t)V𝚏,(𝑭DC,t))V0,(𝑭DC,t)|<εnw.h.p.

Comparing the number of actually frozen variables with the ones marked 𝚏 by WP, we obtain Theorem 2.

2.6 Proving 𝙱𝙿𝙶𝙳 successful

We are left to prove Theorem 1. First, we need to compute the (strictly positive) success probability of 𝙱𝙿𝙶𝙳 for d<dmin. At this point, the fact that 𝙱𝙿𝙶𝙳 has a fair chance of succeeding for d<dmin should not come as a surprise. Indeed, Corollary 9 implies that the BP approximations of the marginals are mostly correct for d<dmin, at least on the formula 𝑭DC,t created by the decimation process. Furthermore, so long as the marginals are correct, the decimation process 𝑭DC,t and the execution of the 𝙱𝙿𝙶𝙳 algorithm 𝑭BP,t move in lockstep. The sole difficulty in analysing 𝙱𝙿𝙶𝙳 lies in proving that the estimates of the algorithm are not just mostly correct, but correct up to only a bounded expected number of discrepancies over the entire execution of the algorithm. To prove this fact we combine the method of differential equations with a subtle analysis of the sources of the remaining bounded number of discrepancies. These discrepancies result from the presence of short (i.e., bounded-length) cycles in the graph G(𝑭). Finally, the proof of the second (negative) part of Theorem 1 follows by coupling the execution of 𝙱𝙿𝙶𝙳 with the decimation process, and invoking Theorem 3. In the next subsection we introduce a simple combinatorial Unit Clause Propagation algorithm to give a glimpse of the proof of the ’positive’ part for the success probability of Theorem 1 for d<dmin. The proof of the second part of the theorem concerning dmin<d<dsat as well as the details of both arguments can be found in the full version.

2.7 Unit Clause Propagation

The simple-minded Unit Clause Propagation algorithm attempts to assign random values to as yet unassigned variables one after the other. After each such random assignment the algorithm pursues the “obvious” implications of its decisions. Specifically, the algorithm substitutes its chosen truth values for all occurrences of the already assigned variables. If this leaves a clause with only a single unassigned variable, a so-called “unit clause”, the algorithm assigns that variable so as to satisfy the unit clause. If a conflict occurs because two unit clauses impose opposing values on a variable, the algorithm declares that a conflict has occurred, sets the variable to false and continues; of course, in the event of a conflict the algorithm will ultimately fail to produce a satisfying assignment. The pseudocode for the algorithm is displayed in Algorithm 3.

Algorithm 3 The 𝚄𝙲𝙿 algorithm.

Let 𝑭UC,t denote the simplified formula obtained after the first t iterations (in which the truth values chosen for x1,,xt and any values implied by Unit Clauses have been substituted). We notice that the values assigned during Steps 6–12 are deterministic consequences of the choices in Step 5. In particular, the order in which unit clauses are processed Steps 6–12 does not affect the output of the algorithm.

Proposition 11.

We have [𝙱𝙿𝙶𝙳 succeeds]=[𝚄𝙲𝙿 succeeds].

Proposition 11 allows us to analyse UCP to prove Theorem 1.

2.8 The success probability of 𝚄𝙲𝙿 for 𝒅<𝒅𝐦𝐢𝐧

We continue to denote by 𝑭UC,t the sub-formula obtained after the first t iterations of 𝚄𝙲𝙿. Let Vn={x1,,xn} be the set of variables of the XORSAT instance F. Also, let 𝑽(t){xt+1,,xn} be the set of variables of 𝑭UC,t. Thus, 𝑽(t) contains those variables among xt+1,,xn whose values are not implied by the assignment of x1,,xt via unit clauses. Also let 𝑪(t) be the set of clauses of 𝑭UC,t; these clauses contain variables from 𝑽(t) only, and each clause contains at least two variables. Let 𝑽¯(t)=Vn𝑽(t) be the set of assigned variables. Thus, after its first t iterations 𝚄𝙲𝙿 has constructed an assignment 𝝈UC:𝑽¯(t){0,1}. Moreover, let 𝑽(t+1)=𝑽(t)𝑽(t+1) be the set of variables that receive values in the course of the iteration t+1 for 0t<n. Additionally, let 𝑪(t+1) be the set of clauses of 𝑭UC,t that consists of variables from 𝑽(t+1) only. Finally, let 𝑭UC,t+1 be the formula comprising the variables 𝑽(t+1) and the clauses 𝑪(t+1).

To characterise the distribution of 𝑭UC,t let 𝒏(t)=|𝑽(t)| and let 𝒎(t) be the number of clauses of length , i.e., clauses that contain precisely variables from 𝑽(t). Observe that 𝒎1(t)=0 because unit clauses get eliminated. Let 𝔉t be the σ-algebra generated by 𝒏(t) and (𝒎(t))2k.

Fact 11.

The XORSAT formula 𝐅UC,t is uniformly random given 𝔉t. In other words, the variables that appear in each clause are uniformly random and independent, as are their signs.

Proof.

This follows from the principle of deferred decisions.

We proceed to estimate the random variables 𝒏(t),𝒎(t). Let 𝜶(t)=|𝑽¯(t)|/n so that 𝒏(t)=n(1𝜶(t)). Recall, that 𝑽¯(t)=Vn𝑽(t). Let λ=λ(θ)=log(1θ) with θt/n and recall that α=α(d,k,λ) denotes the smallest fixed point of ϕd,k,λ. The proof of the following proposition proof can be found in the full version.

Proposition 12.

Suppose that d<dmin(k). There exists a function δ=δ(n)=o(1) such that for all 0t<n and all 2k we have

[|𝜶(t)α|>δ] =O(n2), [|𝒎(t)dnk(k)(1α)αk|>δn] =O(n2). (2.18)

Proposition 12 paves the way for the actual computation of the success probability of 𝚄𝙲𝙿. Let t be the event that a conflict occurs in iteration t. The following proposition gives us the correct value of [t𝔉t] w.h.p.  Since 𝔉t is a random variable the value for the probability [t𝔉t] is random as well.

Proposition 13.

Fix ε>0, let 0t<(1ε)n and define

fn(t)=d(k1)(1α)αk2. (2.19)

Then with probability 1o(1/n) we have

[t𝔉t]=fn(t)24(nt)(1fn(t))2+o(1/n).

The proof of Proposition 13 can be found in Section 2.8.1. Moreover, in the full version we prove the following.

Proposition 14.

Fix ε>0 and 1. For any 0t1<<t<(1ε)n we have

[i=1ti] i=1fn(ti)24(nti)(1fn(ti))2. (2.20)

Finally, the following statement, proven in the full version, deals with the εn final steps of the algorithm.

Proposition 15.

For any δ>0 there exists ε>0 such that [(1ε)n<t<nt]<δ.

Before we proceed we notice that Propositions 1315 imply the first part of Theorem 1.

Proof of Theorem 1 (i).

Pick δ>0, fix a small enough ε=ε(δ)>0 and let 𝑹=t=0n11{t} be the total number of times at which conflicts occur. Proposition 11 shows that the probability that 𝙱𝙿𝙶𝙳 succeeds equals [𝑹=0]. In order to calculate [𝑹=0], let 𝑹ε=0t(1ε)n1{t} be the number of failures before time (1ε)n. Proposition 14 shows that for any fixed 1 we have

𝔼[i=1(𝑹εi+1)] !0t1<<t(1ε)ni=1fn(ti)24(nti)(1fn(ti))2
=(1+o(1))0t1,,t(1ε)ni=1fn(ti)24(nti)(1fn(ti))2𝔼[𝑹ε]. (2.21)

Hence, the inclusion/exclusion principle (e.g., [4, Theorem 1.21]) implies that

[𝑹ε=0] exp(𝔼[𝑹ε]). (2.22)

Further, using Proposition 13 and the linearity of expectation, we obtain with λ(θ)=log(1θ)

𝔼[𝑹ε] 0t(1ε)nfn(t)24(nt)(1fn(t))214n01εfn(θn)2(1θ)(1fn(θn))2dθ
=14n01εfn(θn)2(1α)(1fn(θn))αλλ(θ)θdθ
=d2(k1)2401εz2k4(1z)1d(k1)zk2(1z)dz[by (2.19)]. (2.23)

Finally, Proposition 15 implies that

[𝑹>𝑹ε]<δ. (2.24)

Thus, the assertion follows from (2.22)–(2.24) upon taking the limit δ0.

2.8.1 Proof of Proposition 13

𝑭UC,t+1 is the XORSAT formula that contains the variables 𝑽(t+1) that get assigned during iteration t+1 and the clauses 𝑪(t+1) of 𝑭UC,t that contain variables from 𝑽(t+1) only. Also recall that G(𝑭UC,t+1) signifies the graph representation of this XORSAT formula. Unless 𝑽(t+1)=, the graph G(𝑭UC,t+1) is connected.

Lemma 16.

Fix ε>0 and let 0t(1ε)n. With probability 1o(1/n) the graph G(𝐅UC,t+1) satisfies

|E(G(𝑭UC,t+1))||V(G(𝑭UC,t+1))|.

The proof of Lemma 16 can be found in the full version. Thus, with probability 1o(1/n) the graph G(𝑭UC,t+1) contains at most one cycle. While it is easy to check that no conflict occurs in iteration t+1 if G(𝑭UC,t+1) is acyclic, in the case that G(𝑭UC,t+1) contains a single cycle there is a chance of a conflict. The following definition describes the type of cycle that poses an obstacle.

Definition 17.

For a XORSAT formula F we call a sequence of variables and clauses 𝒞=(v1,c1,,v,c,v+1=v1) a toxic cycle of length if

TOX1

ci contains the variables xi,xi+1 only, and

TOX2

the total number of negations in c1,c is odd iff is even.

Lemma 18.
  1. (i)

    If 𝑭UC,t+1 contains a toxic cycle, then a conflict occurs in iteration t+1.

  2. (ii)

    If 𝑭UC,t+1 contains no toxic cycle and |E(G(𝑭UC,t+1))||V(G(𝑭UC,t+1))|, then no conflict occurs in iteration t+1.

Proof.

Towards (i) we show that 𝑭UC,t+1 is not satisfiable if there is a toxic cycle 𝒞=(v1,c1,,c,v+1=v1); then 𝚄𝙲𝙿 will, of course, run into a contradiction. To see that 𝑭UC,t+1 is unsatisfiable, we transform each of the clauses c1,,c into a linear equation ci(vi+vi+1=yi) over 𝔽2. Here yi𝔽2 equals 1 iff ci contains an even number of negations. Adding these equations up yields i=1yi=0 in 𝔽2. This condition is violated if 𝒞 is toxic.

Let us move on to (ii). Assume for contradiction that there exists a formula F without a toxic cycle such that |V(G(F))||E(G(F))| and such that given 𝑭UC,t+1=F, 𝚄𝙲𝙿 may run into a conflict. Consider such a formula F that minimises |V(F)|+|C(F)|. Since 𝚄𝙲𝙿 succeeds on acyclic F, we have |V(G(F))|=|E(G(F))|. Thus, G(F) contains a single cycle 𝒞=(v1,c1,,v,c,v+1=v1). Apart from the cycle, F contains (possibly empty) acyclic formulas F1,,F attached to v1,,v and F1′′,,F′′ attached to c1,,c. The formulas F1,F1′′,,F,F′′ are mutually disjoint and do not contain unit clauses.

We claim that F1,,F are empty because |V(F)|+|C(F)| is minimum. This is because given any truth assignment of v1,,v, 𝚄𝙲𝙿 will find a satisfying assignment of the acyclic formulas F1,,F.

Further, assume that one of the formulas F1′′,,F′′ is non-empty; say, F1′′ is non-empty. If the start variable that 𝚄𝙲𝙿 assigns were to belong to F1′′, then c1, containing x1 and x2, would not shrink to a unit clause, and thus 𝚄𝙲𝙿 would not assign values to these variables. Hence, 𝚄𝙲𝙿 starts by assigning a truth value to one of the variables v1,,v; say, 𝚄𝙲𝙿 starts with v1. We claim that then 𝚄𝙲𝙿 does not run into a conflict. Indeed, the clauses c2,,c may force 𝚄𝙲𝙿 to assign truth values to x2,,x, but no conflict can ensue because 𝚄𝙲𝙿 will ultimately satisfy c1 by assigning appropriate truth values to the variables of F1′′.

Thus, we may finally assume that all of F1,F1′′,,F,F′′ are empty. In other words, F consists of the cycle 𝒞 only. Since 𝒞 is not toxic, TOX2 does not occur. Consequently, 𝚄𝙲𝙿 will construct an assignment that satisfies all clauses c1,,c. This final contradiction implies (ii).

Corollary 19.

Fix ε>0 and let 0t(1ε)n. Then

[t+1] =[𝑭UC,t+1 contains a toxic cycle]+o(1/n).
Proof.

This is an immediate consequence of Lemma 16 and Lemma 18.

Thus, we are left to calculate the probability that 𝑭UC,t+1 contains a toxic cycle. To this end, we estimate the number of toxic cycles in the “big” formula 𝑭UC,t. Let 𝑻t, be the number of toxic cycles of length in 𝑭UC,t.

Lemma 20.

Fix ε>0 and let 1t(1ε)n.

  1. (i)

    For any fixed , with probability 1O(n2) we have

    𝔼[𝑻t()𝔉t] =β+o(1), where β=14(d(k1)(1α)αk2)=14(fn(t)).
  2. (ii)

    For any 1n, with probability 1O(n2) we have 𝔼[𝑻t()𝔉t]βexp(ε).

The proof of Lemma 20 is provided in the full version.

Proof of Proposition 13.

In light of Corollary 19 we just need to calculate the probability that 𝑭UC,t+1 contains a toxic cycle. Clearly, if during iteration t+1 𝚄𝙲𝙿 encounters a variable of 𝑭UC,t that lies on a toxic cycle, 𝚄𝙲𝙿 will proceed to add the entire toxic cycle to 𝑭UC,t+1 (and run into a contradiction). Furthermore, Lemma 20 shows that with probability 1O(n2) given 𝔉t the probability that a random variable of 𝑭UC,t belongs to a toxic cycle comes to

β¯ =2β+o(1)=214(fn(t))=fn(t)24(1fn(t))+o(1)=O(1). (2.25)

We now use (2.25) to calculate the desired probability of encountering a toxic cycle. To this end we notice that the (t+1)-st iteration of 𝚄𝙲𝙿 corresponds to a branching process with expected offspring fn(t), unless the root variable xt+1 has already been assigned. With probability 1O(n2) the conditional probability of this latter event equals (nαt)/(nt)+o(1). Further, given that the root variable has not been assigned previously, the expected progeny of the branching process, i.e., the expected number of variables in 𝑭UC,t+1, equals 1/(1fn(t))+o(1). Since with probability 1O(n2) given 𝔉t there remain 𝒏(t)=(1α+o(1))n unassigned variables in total, (2.25) implies that with probability 1o(1/n),

[t+1𝔉t] β¯(1α)n1α1t/n11fn(t)=fn(t)24(1fn(t))2(nt)+o(1/n),

as claimed.

3 Discussion

The thrust of the present work is to verify the predictions from [24] on the 𝙱𝙿𝙶𝙳 algorithm and the decimation process rigorously. Concerning the decimation process, the main gap in the deliberations of Ricci-Tersenghi and Semerjian [24] that we needed to plug is the proof of Proposition 8 on the actual number of null variables in the decimation process. The proof of Proposition 8, in turn, hinges on the formula for the nullity from Proposition 6, whereas Ricci-Tersenghi and Semerjian state the (as it turns out, correct) formulas for the nullity and the number of null variables based on purely heuristic arguments.

Regarding the analysis of the 𝙱𝙿𝙶𝙳 algorithm, Ricci-Tersenghi and Semerjian state that they rely on the heuristic techniques from the insightful article [10] to predict the formula (1.7), but do not provide any further details; the article [10] principally employs heuristic arguments involving generating functions. By contrast, the method that we use to prove (1.7) is a bit more similar to that of Frieze and Suen [12] for the analysis of a variant of the unit clause algorithm on random k-SAT instances, for which they also obtain the asymptotic success probability. Yet by comparison to the argument of Frieze and Suen, we pursue a more combinatorially explicit approach that demonstrates that certain small sub-formulas that we call “toxic cycles” are responsible for the failure of 𝙱𝙿𝙶𝙳. Specifically, the proof of (1.7) combines the method of differential equations with Poissonisation. Finally, the proof of Theorem 1 (ii) is an easy afterthought of the analysis of the decimation process.

Yung’s work [25] on random k-XORSAT is motivated by the “overlap gap paradigm” [13], the basic idea behind which is to show that a peculiar clustered geometry of the set of solutions is an obstacle to certain types of algorithms. Specifically, Yung only considers the Unit Clause Propagation algorithm and (a truncated version of) 𝙱𝙿𝙶𝙳. Following the path beaten in [19], Yung performs moment computations to establish the overlap gap property. However, moment computations (also called “annealed computations” in physics jargon) only provide one-sided bounds. Yung’s results require spurious lower bounds on the clause length k (k9 for Unit Clause and k13 for 𝙱𝙿𝙶𝙳). By contrast, the present proof strategy pivots on the number of null variables rather than overlaps, and Proposition 8 provides the precise “quenched” count of null variables. A further improvement over [25] is that the present analysis pinpoints the precise threshold up to which 𝙱𝙿𝙶𝙳 (as well as Unit Clause) succeeds for any k3. Specifically, Yung proves that these algorithms fail for d>dcore, while Theorem 1 shows that failure occurs already for d>dmin with dmin<dcore. Conversely, Theorem 1 shows that the algorithms succeed with a non-vanishing probability for d<dmin. Thus, Theorem 1 identifies the correct threshold for the success of 𝙱𝙿𝙶𝙳, as well as the correct combinatorial phenomenon that determines this threshold, namely the onset of reconstruction in the decimation process (Theorems 2 and 3).

The 𝙱𝙿𝙶𝙳 algorithm as detailed in Section 2.2 applies to a wide variety of problems beyond random k-XORSAT. Of course, the single most prominent example is random k-SAT. Lacking the symmetries of XORSAT, random k-SAT does not allow for the simplification to discrete messages; in particular, the BP messages are not generally half-integral. In effect, BP and WP are no longer equivalent. In addition to random k-XORSAT, the article [24] also provides a heuristic study of 𝙱𝙿𝙶𝙳 on random k-SAT. But once again due to the lack of half-integrality, the formulas for the phase transitions no longer come as elegant finite-dimensional expressions. Instead, they now come as infinite-dimensional variational problems. Furthermore, the absence of half-integrality also entails that the present proof strategy does not extend to k-SAT.

The lack of inherent symmetry in random k-SAT can partly be compensated by assuming that the clause length k is sufficiently large (viz. larger than some usually unspecified constant k0). Under this assumption the random k-SAT version of both the decimation process and the 𝙱𝙿𝙶𝙳 algorithm have been analysed rigorously [7, 9]. The results are in qualitative agreement with the predictions from [24]. In particular, the 𝙱𝙿𝙶𝙳 algorithm provably fails to find satisfying assignments on random k-SAT instances even below the threshold where the set of satisfying assignments shatters into well-separated clusters [1, 16]. Furthermore, on random k-SAT a more sophisticated message passing algorithm called Survey Propagation Guided Decimation has been suggested [20, 24]. While on random XORSAT Survey Propagation and Belief Propagation are equivalent, the two algorithms are substantially different on random k-SAT. One might therefore hope that Survey Propagation Guided Decimation outperforms 𝙱𝙿𝙶𝙳 on random k-SAT and finds satisfying assignments up to the aforementioned shattering transition. A negative result to the effect that Survey Propagation Guided Decimation fails asymptotically beyond the shattering transition point for large enough k exists [14]. Yet a complete analysis of Belief/Survey Propagation Guided Decimation on random k-SAT for any k3 in analogy to the results obtained here for random k-XORSAT remains an outstanding challenge.

Finally, returning to random k-XORSAT, a question for future work may be to investigate the performance of various types of algorithms such as greedy, message passing or local search that aim to find an assignment that violates the least possible number of clauses. Of course, this question is relevant even for d>dsat(k). A first step based on the heuristic “dynamical cavity method” was recently undertaken by Maier, Behrens and Zdeborová [17].

References

  • [1] Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In Proc. 49th FOCS, pages 793–802, 2008. doi:10.1109/FOCS.2008.11.
  • [2] Dimitris Achlioptas and Micheal Molloy. The solution space geometry of random linear equations. Random Structures & Algorithms, 46:197–231, 2015. doi:10.1002/RSA.20494.
  • [3] Peter Ayre, Amin Coja-Oghlan, Pu Gao, and Noëla Müller. The satisfiability threshold for random linear equations. Combinatorica, 40:179–235, 2020. doi:10.1007/S00493-019-3897-3.
  • [4] Béla Bollobás. Random Graphs. Cambridge University Press, 2001.
  • [5] Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina. Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms, 27:201–226, 2005. doi:10.1002/RSA.20057.
  • [6] Amin Coja-Oghlan. A better algorithm for random k-sat. SIAM Journal on Computing, 39:2823–2864, 2010. doi:10.1137/09076516X.
  • [7] Amin Coja-Oghlan. Belief propagation guided decimation fails on random formulas. Journal of the ACM, 63(49), 2017. doi:10.1145/3005398.
  • [8] Amin Coja-Oghlan, Alperen A. Ergür, Pu Gao, Samuel Hetterich, and Maurice Rolvien. The rank of sparse random matrices. Random Structures & Algorithms, 62:68–130, 2023. doi:10.1002/RSA.21085.
  • [9] Amin Coja-Oghlan and Angelica Pachon-Pinzon. The decimation process in random k-sat. SIAM Journal on Discrete Mathematics, 26:1471–1509, 2012. doi:10.1137/110842867.
  • [10] Christophe Deroulers and Rémi Monasson. Criticality and universality in the unit-propagation search rule. European Physical Journal B., 49:339–369, 2006.
  • [11] Olivier Dubois and Jacques Mandler. The 3-xorsat threshold. In Proc. 43rd FOCS, pages 769–778, 2002. doi:10.1109/SFCS.2002.1182002.
  • [12] Alan Frieze and Stephen Suen. Analysis of two simple heuristics on a random instance of k-sat. Journal of Algorithms, 20:312–355, 1996. doi:10.1006/JAGM.1996.0016.
  • [13] David Gamarnik. The overlap gap property: a topological barrier to optimizing over random structures. Proceeding of the National Academy of Sciences, 118, 2021.
  • [14] Samuel Hetterich. Analysing survey propagation guided decimation on random formulas. In Proc. 43rd ICALP, number 65, 2016.
  • [15] Morteza Ibrahimi, Yash Kanoria, Matt Kraning, and Andrea Montanari. The set of solutions of random xorsat formulae. Annals of Applied Probability, 25:2743–2808, 2015.
  • [16] Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceeding of the National Academy of Sciences, 104:10318–10323, 2007. doi:10.1073/PNAS.0703685104.
  • [17] Aude Maier, Freya Behrens, and Lenka Zdeborová. Dynamical cavity method for hypergraphs and its application to quenches in the k-xorsat problem, 2024. arXiv:2412.14794.
  • [18] Marc Mézard and Andrea Montanari. Information, Physics and Computation. Oxford University Press, 2009.
  • [19] Marc Mézard, Thierry Mora, and Riccardo Zecchina. Clustering of solutions in the random satisfiability problem. Physical Review Letters, 94, 2005.
  • [20] Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297:812–815, 2002.
  • [21] Marc Mézard, Federico Ricci-Tersenghi, and Riccardo Zecchina. Two solutions to diluted p-spin models and xorsat problems. Journal of Statistical Physics, 111:505–533, 2003.
  • [22] Michael Molloy. Cores in random hypergraphs and boolean formulas. Random Structures & Algorithms, 27:124–135, 2005. doi:10.1002/RSA.20061.
  • [23] Boris Pittel and Gregory B. Sorkin. The satisfiability threshold for k-xorsat. Combinatorics, Probability and Computing, 25:236–268, 2016. doi:10.1017/S0963548315000097.
  • [24] Federico Ricci-Tersenghi and Guilhem Semerjian. On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms. Journal of Statistical Mechanics, 2009.
  • [25] Kingsley Yung. Limits of sequential local algorithms on the random k-xorsat problem. In Proc. 51st ICALP, number 123, 2024.