CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation

Luis E. Ortiz ¨ ECE Dept, Univ. of Puerto Rico, Mayaguez, PR 00681-9042 leortiz@ece.uprm.edu

Abstract
This paper proposes constraint propagation relaxation (CPR), a probabilistic approach to classical constraint propagation that provides another view on the whole parametric family of survey propagation algorithms SP(). More importantly, the approach elucidates the implicit, but fundamental assumptions underlying SP(), thus shedding some light on its effectiveness and leading to applications beyond k -SAT.

1

Introduction

Survey propagation (SP) is an algorithm for solving k -SAT recently developed in the physics community [1, 2] that exhibits excellent empirical performance on "hard" instances. To understand the behavior of SP and its effectiveness, recent work (see Maneva et al. [3] and the references therein) has concentrated on establishing connections to belief propagation (BP) [4], a well-known approximation method for computing posterior probabilities in probabilistic graphical models. Instead, this paper argues that it is perhaps more natural to establish connections to constraint propagation (CP), another message-passing algorithm tailored to constraint satisfaction problems (CSPs) that is wellknown in the AI community. The ideas behind CP were first proposed by Waltz [5] 1 Yet, CP has received considerably less attention than BP lately. This paper reconnects BP to CP in the context of CSPs by proposing a probabilistic relaxation of CP that generalizes it. Through the approach, it is easy to see the exact, implicit underlying assumptions behind the entire family of survey propagation algorithms SP(). (Here, the approach is presented in the context of k -SAT; it will be described in full generality in a separate document.) In short, the main point of this paper is that survey propagation algorithms are instances of a natural generalization of constraint propagation and have simple interpretations in that context.

2

Constraint Networks and Propagation

This section presents a brief introduction to the graphical representation of CSPs and CP, and concentrates on the aspects that are relevant to this paper. 2 A constraint network (CN) is the graphical model for CSPs used in the AI community. Of interest here is the CN based on the hidden transformation. (See Bacchus et al. [9] for more information on the different transformations and their properties.) It has a bipartite graph where every variable and constraint is each represented by a node or vertex in the graph and there is an edge between a variable i and a constraint a if and only if a is a function of i (see figure 1). From now on, a CN with a tree graph is referred to as a tree CN, and a CN with an arbitrary graph as an arbitrary CN.
See also Pearl [4], section 4.1.1, and the first paragraph of section 4.1.2. Please refer to Russell and Norvig [6] for a general introduction, Kumar [7] for a tutorial and Dechter [8] for a more comprehensive treatment of these topics and further references.
2 1

1


Constraint propagation is typically used as part of a depth-first search algorithm for solving CSPs. The search algorithm works by extending partial assignments, usually one variable at a time, during the search. The algorithm is called backtracking search because one can backtrack and change the value of a previously assigned variable when the search reaches an illegal assignment.

variables 1 2 3 4

CP is often applied either as a preprocessing a b step or after an assignment to a variable is made. The objective is to reduce the domains clauses of the variables by making them locally consistent with the current partial assignment. The Figure 1: The graph of the constraint network corpropagation process starts with the belief that responding to the 3-SAT formula f (x) = (x1  for every value assignment vi in the domain of x2  x3 )  (x2  x3  x4 ), which has four variŻ each variable i there exists a solution with vi asables and two clauses; the first and second clause signed to i. The process then attempts to correct are denoted in the figure by a and b, respectively. this a priori belief by locally propagating conFollowing the convention of the SP community, straint information. It is well-known that CP, clause and variable nodes are drawn as boxes and unlike BP, always converges, regardless of the circles, respectively; also, if a variable appears as structure of the CN graph. This is because no a negative literal in a clause (i.e., variable 3 in possible solution is ignored at the start and none clause b), the edge between them is drawn as a ever removed during the process. In the end, CP dashed line. produces potentially reduced variable domains that are in fact locally consistent. In turn, the resulting search space is at worst no larger than the original but potentially smaller while still containing all possible solutions. The computational efficiency and effectiveness of CP in practice has made it a popular algorithm in the CSP community.

3

Terminology and Notation

Let V (a) be the set of variables that appear in constraint a and C (i) the set of constraints in variables which variable i appears. Let also Vi (a)  1 2 3 4 V (a) - {i} and Ca (i)  C (i) - {a}. In k SAT, the constraints are the clauses, each variable is binary, with domain {0, 1}, and a solution corresponds to a satisfying assignment. If i  V (a), denote by sa,i the value assignment f_b to variable i that guarantees the satisfiability of f_{b -> 2} a b clause a; and denote the other possible assignclauses s u ment to i by ua,i . Finally, let Ca (i) and Ca (i) be the set of clauses in Ca (i) where variable i appears in the same and different literal form as Figure 2: The graph inside the continuous curve is the CN graph for the formula fb that results from it does in clause a, respectively. removing clause b from f . The graph inside the The k -SAT formula under consideration is de- dashed curve is the CN graph for f b2 , which cornoted by f . It is convenient to introduce no- responds to the formula for the connected compotation for formulae associated to the CN that nent of the CN graph for f that contains variable b results from removing variables or constraints 2. from f . Let fa be the function that results from removing clause a from f (see figure 2), and similarly, abusing notation, let fi be the function that results from removing variable i from f . Let fai be the function that corresponds to the connected component of the CN graph for fa that contains variable i  V (a), and let fia be the function that corresponds to the connected component of the CN graph for fi that contains a  C (i). (Naturally, if node a is not a separator of the CN graph for f , fa has a single connected component, which leads to fai = fa ; similarly for fi .) 2


It is convenient to use a simple, if perhaps unusual, representation of sets in order to track the domains of the variables during the propagation process. Each subset A of a set S of size m is represented as a bit array of m elements where component k in the array is set to 1 if k is in A and to 0 otherwise. For instance, if S = {0, 1}, then the array [00] represents , and similarly, [01], [10] and [11] represent {0}, {1} and {0, 1}, respectively. It is also useful to introduce the concept of (globally) consistent domains of variables and SAT functions. Let Sf = {x|x satisfies f } be the set of assignments that satisfy f . Given a complete assignment x, denote by x-i the assignments to all the variables except i; thus, x = (x1 , . . . , xn ) = (xi , x-i ). Let the set Wi be the consistent domain of variable i in f if Wi = {xi |x = (xi , x-i )  Sf for some x-i }; that is, Wi contains the set of all possible values that variable i can take in an assignment that satisfies f . Let the set W be the consistent domain of f if W = ×n 1 Wi and, for i= all i, Wi is the consistent domain of variable i in f . Finally, some additional terminology classifies variables of a SAT function given a satisfying assignment. Given a function f and a satisfying assignment x, let variable i be fixed if changing only its assignment xi in x does not produce another satisfying assignment for f ; and be free otherwise.

4

Propagation Algorithms for Satisfiability

Constraint Propagation. In CP for k -SAT, the message Mai that clause a sends to variable i is an array of binary values indexed by the elements of the domain of i; similarly, for the message Mia that variable i sends to clause a. Intuitively, for all xi  {0, 1}, Mia (xi ) = 1 if and only if assigning value xi to variable i is "ok" with all clauses other than a. Formally, Mia (xi ) = 1 if and only if fai has a satisfying assignment with xi assigned to variable i (or in other words, xi is in the consistent domain of i in fai ). Similarly, Mai (xi ) = 1 if and only if clause a is "ok" with assigning value xi to variable i; or formally, Mai (xi ) = 1 if and only if fia has a satisfying assignment with xi assigned to variable i, or assigning xi to variable i by itself xi xi satisfies a. It is convenient to denote Mia (xi ) and Mia (xi ) by Mai and Mai , respectively. sa,i ua,i sa,i ua,i s s In addition, Mia , Mia , Mai and Mai are simply denoted by Mia , Miu a , Mai and  u Mai , respectively. In summary, we can write CP for k -SAT as follows. · Messages that clause a sends to variable i:
xi s Mai = 1 if and only if xi = sa,i or, there exists j  Vi (a), s.t. Mj a = 1.

(1)

· Messages that variable i sends to clause a:
xi Mixi a = 1 if and only if for all b  Ca (i), Mbi = 1. 

(2)

It is convenient to express CP mathematically as follows. · Messages that clause a sends to variable i: 1 , xi j Mai = 1- (1 - M s
Vi (a)

j a ),

if xi = sa,i , if xi = ua,i .
xi Mbi .

· Messages that variable i sends to clause a: Mixi a = 

b

Ca (i)

In order to guarantee convergence, the message values in CP are initialized as Mis a = 1, Miu a =   u s 1, Mai = 1, and naturally, Mai = 1. This initialization encodes the a priori belief that every assignment is a solution. CP attempts to "correct" or update this belief through the local propagation of constraint information. In fact, the expressions in CP force the messages to be locally consistent. By being initially conservative about the consistent domains, no satisfying assignment is discarded during the propagation process. Once aCP converges, for each avariable i, its locally-consistent domain becomes xi u {0,1} {xi | . For general CSPs, C (i) Mai = 1} = {xi | C (i):xi =ua,i Mai = 1}  2 CP is usually very effective because it can significantly reduce the original domain of the variables, 3


leading to a smaller search space of possible assignments. It should be noted that in the particular case of k -SAT with arbitrary CNs, CP is usually only effective after some variables have already being assigned during the search, because those (partial) assignments can lead to "boundary conditions." Without such boundary conditions, however, CP never reduces the domain of the variables in k -SAT, as can be easily seen from the expressions above. On the other hand, when CP is applied to tree CNs, it exhibits additional special properties. For example, convergence is actually guaranteed regardless of how the messages are initialized, because of the boundary conditions imposed by the leaves of the tree. Also, the final messages are in fact globally consistent (i.e., all the messages are consistent with their definition). Therefore, the locallyconsistent domains are in fact the consistent domains. Whether the formula is satisfiable, or not, can be determined immediately after applying CP. If the formula is not satisfiable, the consistent domains will be empty sets. If the formula is in fact satisfiable, applying depth-first search always finds a satisfying assignment without the need to backtrack. We can express CP in a way that looks closer to SP and BP. Using the reparametrization ai = u 1 - Mai , we get the following expression of CP. j s · Message that clause a sends to variable i: ai = Vi (a) (1 - Mj a ). b · Message that variable i sends to clause a: Mis a =  C u (i) (1 - bi ).
a

Survey Propagation. Survey propagation has become a very popular propagation algorithm for ´ k -SAT. It was developed in the physics community by Mezard et al. [2]. The excitement around SP comes from its excellent empirical performance on hard satisfiability problems; that is, k -SAT formulae with a ratio  of the number of clauses to the number of variables near the so called satisfiability threshold c . The following is a description of an SP-inspired family of message-passing procedures, parametrized by   [0, 1]. It is often denoted by SP(), and contains BP ( = 0) and (pure) SP ( = 1). · Message that clause a sends to variable i: j ai = Vi (a)

ua j ua +sa +a j j j

· Messages that variable i sends to clause a: 1 b b ua = -  C u (i) (1 - bi ) s i Ca (i) (1 - bi ) a 1  b b sa = - u s i Ca (i) (1 - bi ) Ca (i) (1 - bi ) b b b  ia = C u (i) (1 - bi ) C s (i) (1 - bi ) = Ca (i) (1 - bi )
a a

SP was originally derived via arguments and concepts from physics. A simple derivation based on a probabilistic interpretation of CP is given in the next section of the paper. The derivation presented here elucidates the assumptions that SP algorithms make about the satisfiability properties and structure of k -SAT formulae. However, it is easy to establish strong equivalence relations between the different propagation algorithms even at the basic level, before introducing the probabilistic interpretation (details omitted).

5

A Probabilistic Relaxation of Constraint Propagation for Satisfiability

The main idea behind constraint propagation relaxation (CPR) is to introduce a probabilistic model for the k -SAT formula and view the messages as random variables in that model. If the formula f has n variables, the sample space  = (2{0,1} )n is the set of the n-tuple whose components are subsets of the set of possible values that each variable i can take (i.e., subsets of {0, 1}). The "true probability law" Pf of a SAT formula f that corresponds to CP is defined in terms of the consistent domain of f : for all W  , 1 , if W is the consistent domain of f , Pf (W ) = 0, otherwise. 4


Clearly, if we could compute the consistent domains of the remaining variables after each variable assignment during the search, there would be no need to backtrack. But, while it is easy to compute consistent domains for tree CNs, it is actually hard in general for arbitrary CNs. Thus, it is generally hard to compute Pf . (CNs with graphs of bounded tree-width are a notable exception.) However, the probabilistic interpretation will allow us to introduce "bias" on , which leads to a heuristic for dynamically ordering both the variables and their values during search. As shown in this section, it turns out that for arbitrary CNs, survey propagation algorithms attempt to compute different "approximations" or "relaxations" of Pf by making different assumptions about its "probabilistic structure."
s u Let us now view each message Mai , Mai , Mis a , and Miu a for each variable i and clause   a as a (Bernoulli) random variable in some probabilistic model with sample space  and a, now arbitrary, probability law P. 3 Formally, for each clause a, variable i and possible assignment value xi  {0, 1}, we define xi i i Mai  Bernoulli(pxi ) and Mixi a  Bernoulli(pxa ) i  a xi xi xi xi where pai = P(Mai = 1) and pia = P(Mia = 1). This is a distribution over all possible subsets (i.e., the power set) of the domain of each variable, not just over the variable's domain itself. s Also, clearly we do not need to worry about ps i because it is always 1, by the definition of Mai . a

The following is a description of how we can use those probabilities during search. In the SP community, the resulting heuristic search is called "decimation" [1, 2]. If we believe that P "closely xi approximates" Pf , and know the probability pxi  P(Mai = 1 for all a  C (i)) that xi is in i the consistent domain for variable i of f , for every variable i, clause a and possible assignment xi , we can use them to dynamically order both the variables and the values they can take during u u search. Specifically, we first compute p1 = P(Mai = 1 for all a  C - (i)) and p0 = P(Mai = i i + + - 1 for all a  C (i)) for each variable i, where C (i) and C (i) are the sets of clauses where variable i appears as a positive and a negative literal, respectively. Using those probability values, we then compute what the SP community calls the "bias" of i: |p1 - p0 |. The variable to assign next i i is the one with the largest bias. 4 We would set that variable to the value of largest probability; for instance, if variable i has the largest bias, then we set i next, to 1 if p1 > p0 , and to 0 if p1 < p0 . i i i i The objective is then to compute or estimate those probabilities. The following are (independence) assumptions about the random variables (i.e., messages) used in this section. The assumptions hold for tree CNs and, as formally shown below, are inherent to the survey propagation process. s Assumption 1. For each clause a and variable i, the random variables Mj a for all j  Vi (a) are independent. u Assumption 2. For each clause a and variable i, the random variables Mbi for all clauses b  u Ca (i) are independent. u Assumption 3. For each clause a and variable i, the random variables Mbi for all clauses b  s Ca (i) are independent. Without any further assumptions, we can derive the following, by applying assumption 1 and the u expression for Mai that results from 1: j j u s s pui = P(Mai = 1) = 1 - a Vi (a) P(Mj a = 0) = 1 - Vi (a) (1 - pj a ). Similarly, by assumption 2 and the expression for Mis a that results from 2, we derive  b b u u psa = P(Mis a = 1) = u u i  Ca (i) P(Mbi = 1) = Ca (i) pbi .
u Using the reparametrization ai = P(Mai = 0) = 1 - pui , we obtain the following messagea passing procedure.
3 Given clause a and variable i of SAT formula f , let Dai,j be the (globally) consistent domain of fai for variable j . The random variables corresponding to the messages from variable i to clause a are defined as Mixi a (W ) = 1 iff W|  Dai,j for every variable j of fai ; and xi  Dai,i . The other random variables  Q s u s are then defined as Mai (W ) = 1 and Mai (W ) = 1 - j Vi (a) (1 - Mj a (W )) for all W . 4 For both variable and value ordering, we can break ties uniformly at random. Also, the description of SP() used often, sets a fraction  of the variables that remain unset during search. While clearly this speeds up the process of getting a full assignment, the effect that heuristic might have on the completeness of the search procedure is unclear, even in practice.

5


· Message that clause a sends to variable i: ai = · Message that variable i sends to clause a: psa = i We can then use assumption 3 to estimate pua as i b
s Ca (i) (1

j b

Vi (a) (1
u Ca (i) (1

- psa ) i - bi )

- bi ).

Note that this message-passing procedure is exactly "classical" CP if we initialize ai = 0 and psa = 1 for all variables i and clause a. However, the version here allows the messages to be in i [0, 1]. At the same time, for tree CNs, this algorithm is the same as classical CP (i.e., produces the same result), regardless of how the messages ai and psa are initialized. In fact, in the tree case, i the final messages uniquely identify P = Pf . Making Assumptions about Satisfiability. Let us make the following assumption about the "probabilistic satisfiability structure" of the k -SAT formula. Assumption 4. For some   [0, 1], for each clause a and variable i, P(Mis a = 0, Miu a = 0) = (1 - )P(Mis a = 1, Miu a = 1).     For  = 1, the last assumption essentially says that fai has a satisfying assignment; i.e., P(Mis a = 0, Miu a = 0) = 0. For  = 0, it essentially says that the likelihood that fai does   not have a satisfying assignment is the same as the likelihood that fai has a satisfying assignment where variable i is free. Formally, in this case, we have P(Mis a = 0, Miu a = 0) = P(Mis a =    1, Miu a = 1), which, interestingly, is equivalent to the condition P(Mis a = 1) + P(Miu a =    1) = 1. Let us introduce a final assumption about the random variables associated to the messages from variables to clauses. Assumption 5. For each clause a and variable i, the random variables Mis a and Miu a are   independent. Note that assumptions 2, 3 and 5 hold (simultaneously) if and only if for each clause a and variable u i, the random variables Mbi for all clauses b  Ca (i) are independent. The following theorem is the main result of this paper. Theorem 1. (Sufficient Assumptions) Let assumptions 1, 2 and 3 hold. The message-passing procedure that results from the probabilistic approach to constraint propagation presented above is 1. belief propagation (i.e., SP(0)), if assumption 4, with  = 0, holds, and 2. a member of the family of survey propagation algorithms SP(), with 0 <   1, if assumption 4, with the given , and assumption 5 hold. These assumptions are also necessary in a strong sense (details omitted), Assumptions 1, 2, 3, and even 5 might be obvious to some readers, but assumption 4 might not be, and it is essential. j s Proof. As in the last subsection, assumption 1 leads to pui = 1 - a Vi (a) (1 - pj a ), while b b s u u u assumptions 2 and 3 lead to pia = u s Ca (i) pbi and pia = Ca (i) pbi . Note also that assumption 4 is equivalent to psa + pua -  P(Mis a = 1, Miu a = 1) = 1. This i i   allows us to express psa i , P(Mis a = 1) = psa = s  i u pia + pia -  P(Mis a = 1, Miu a = 1)   which implies P(Mis a = 0) =  pua i pua -  P(Mis a = 1, Miu a = 1) i   . -  P(Mis a = 1, Miu a = 1) + psa   i pua i . pua + psa i i

If  = 0, then the last expression simplifies to P(Mis a = 0) =  6


u Using the reparametrization ai  P(Mai = 0) = 1 - pui , ua  P(Miu a = 1) = pua i  i a and sa + a  P(Mis a = 1) = psa , leads to BP (i.e., SP(0)). i  i i u Otherwise, if 0 <   1, then using the reparametrization ai  P(Mai = 0),

ua i sa i a i

 =  

P(Miu a  P(Mis a  P(Mis a  P(Mis a 

= 1) -  P(Mis a = 1, Miu a = 1)   = 0, Miu a = 1) + (1 - )P(Mis a = 1, Miu a = 1),    = 1, Miu a = 0), and  = 1, Miu a = 1), 

and applying assumption 5 leads to SP(). The following are some remarks that can be easily derived using CPR. On the Relationship Between SP and BP. SP essentially assumes that every sub-formula fai has a satisfying assignment, while BP assumes that for every clause a and variable i  V (a), variable i is equally likely not to have a satisfying assignment or being free in fai , as it is easy to see from assumption 4. The parameter  just modulates the relative scaling of those two likelihoods. While the same statement about pure SP is not novel, the statement about BP, and more generally, the class SP() for 0   < 1, seems to be. On the Solutions of SAT formula f . Note that Pf may not satisfy all or any of the assumptions. Yet, satisfying an assumption imposes constraints on what Pf actually is and thus on the solution space of f . For example, if Pf satisfies assumption 4 for any  < 1, which includes BP when  = 0, and for all clauses a and variables i, then Pf (Mis a = 0, Miu a = 0) = Pf (Mis a = 1, Miu a =     1) = 0 and therefore either Pf (Mis a = 1, Miu a = 0) = 1 or Pf (Mis a = 0, Miu a = 1) = 1     holds, but not both, of course. That implies f must have a unique solution! On SP. This result provides additional support to previous informal conjectures as to why SP is so effective near the satisfiability threshold: SP concentrates all its efforts on finding a satisfying assignment when they are scarce and "scattered" across the space of possible assignments. Thus, SP assume that the set of satisfying assignments has in fact special structure. To see that, note that assumptions 4, with  = 1, and 5 imply that P(Mis a = 1, Miu a = 0) = 0   or P(Mis a = 0, Miu a = 1) = 0 must hold. This says that in every assignment that satisfies   fai , variable i is either free or always has the same value assignment. This observation is relevant because it has been argued that as we approach the satisfiability threshold, the set of satisfying assignments decomposes into many "local" or disconnected subsets. It follows easily from the discussion here that SP assumes such a structure, therefore potentially making it most effective under those conditions (see Maneva et al. [3] for more information). Similarly, it has also been empirically observed that SP is more effective for  close to, but strictly less than 1. The CPR approach suggests that such behavior might be because, with respect to any P that satisfies assumption 4, unlike pure SP, for such values of  < 1, SP() guards against the possibility that fai is not satisfiable, while still being somewhat optimistic by giving more weight to the event that variable i is free in fai . Naturally, BP, which is the case of  = 0, might be too pessimistic in this sense. On BP. For BP ( = 0), making the additional assumption that the formula fai is satisfiable (i.e., P(Mis a = 0, Miu a = 0) = 0) implies that there are no assignments with free variables (i.e.,   P(Mis a = 1, Miu a = 1) = 0). Therefore, the only possible consistent domain is the singleton   {sa,i } or {ua,i } (i.e., P(Mis a = 1, Miu a = 0) + P(Mis a = 0, Miu a = 1) = 1). Thus,     either 0 or 1 can possibly be a consistent value assignment, but not both. This suggests that BP is concentrating its efforts on finding satisfying assignments without free variables. On Variable and Value Ordering. To complete the picture of the derivation of SP() via CPR, we need to compute p0 and p1 for all variables i to use for variable and value ordering during search. i i We can use the following, slightly stronger versions of assumptions 2 and 3 for that. u Assumption 6. For each variable i, the random variables Mai for all clauses a  C - (i) are independent. 7


u Assumption 7. For each variable i, the random variables Mai for all clauses a  C + (i) are independent. a 0 Using assumptions 6 and 7, we can easily derive that p1 = i C - (i) (1 - ai ) and pi = a C + (i) (1 - ai ), respectively.

On Generalizations. The approach provides a general, simple and principled way to introduce possibly uncertain domain knowledge into the problem by making assumptions about the structure of the set of satisfying assignments and incorporating them through P. That can lead to more effective propagation algorithms for specific contexts. Related Work. Dechter and Mateescu [10] also connect BP to CP but in the context of the inference problem of assessing zero posterior probabilities. Hsu and McIlraith [11] give an intuitive explanation of the behavior of SP and BP from the perspective of traditional local search methods. They provide a probabilistic interpretation, but the distribution used there is over the biases. Braunstein and Zecchina [12] showed that pure SP is equivalent to BP on a particular MRF over an extended domain on the variables of the SAT formula, which adds a so called "joker" state. Maneva et al. [3] generalized that result by showing that SP() is only one of many families of algorithms that are equivalent to performing BP on a particular MRF. In both cases, one can easily interpret those MRFs as ultimately imposing a distribution over , as defined here, where the joker state corresponds to the domain {0, 1}. Here, the only particular distribution explicitly defined is Pf , the "optimal" distribution. This paper does not make any explicit statements about any specific distribution P for which applying CPR leads to SP().

6

Conclusion

This paper strongly connects survey and constraint propagation. In fact, the paper shows how survey propagation algorithms are instances of CPR, the probabilistic generalization of classical constraint propagation proposed here. The general approach presented not only provides a new view on survey propagation algorithms, which can lead to a better understanding of them, but can also be used to easily develop potentially better algorithms tailored to specific classes of CSPs.

References
´ [1] A. Braunstein, M. Mezard, and R. Zecchina. Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms, 27:201, 2005. ´ [2] M. Mezard, G. Parisi, and R. Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems. Science, 297(5582):812­815, 2002. [3] E. Maneva, E. Mossel, and M. J. Wainwright. A new look at survey propagation and its generalizations. ACM, 54(4):2­41, July 2007. [4] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Networks of Plausible Inference. Morgan Kaufmann, 1988. [5] D. L. Waltz. Generating semantic descriptions from drawings of scenes with shadows. Technical Report 271, MIT AI Lab, Nov. 1972. PhD Thesis. [6] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach, chapter 5, pages 137­160. Prentice Hall, second edition, 1995. [7] V. Kumar. Algorithms for constraint-satisfaction problems: A survey. AI Magazine, 13(1):32­44, 1992. [8] R. Dechter. Constraint Processing. Morgan Kaufmann, 2003. [9] F. Bacchus, X. Chen, P. van Beek, and T. Walsh. Binary vs. non-binary constraints. AI, 140(1-2):1­37, Sept. 2002. [10] R. Dechter and R. Mateescu. A simple insight into iterative belief propagation's success. In UAI, 2003. [11] E. I. Hsu and S. A. McIlraith. Characterizing propagation methods for boolean satisfiability. In SAT, 2006. [12] A. Braunstein and R. Zecchina. Survey propagation as local equilibrium equations. JSTAT, 2004.

8