Search Results

This chapter studies two problems of statistical physics: the ferromagnet and the spin glass, on large random graphs with fixed degree profile. It describes the use of the replica symmetric cavity method in this context, and studies its stability. The analysis relies on physicists methods, without any attempt at being rigorous. It provides a complete solution of the ferromagnetic problem at all temperatures. In the spin glass case, the replica symmetric solution is asymptotically correct in the high temperature ‘paramagnetic’ phase, but it turns out to be wrong in the spin glass phase. The phase transition temperature can be computed exactly.

This chapter discusses the use of message passing techniques in a combinatorial optimization problem assignment. Given N ‘agents’ and N ‘jobs’, and the cost matrix E(i,j) for having job i executed by agent j, the problem is to find the lowest cost assignment of jobs to agents. On the algorithmic side, the Min-Sum variant of Belief Propagation is shown to converge to an optimal solution in polynomial time. On the probabilistic side, the large N limit of random instances, when the costs E(i,j) are independent uniformly random variables, is studied analytically. The cost of the optimal assignment is first computed heuristically within the replica symmetric cavity method, giving the celebrated zeta(2) result. This study is confirmed by a rigorous combinatorial argument which provides a proof of the Parisi and Coppersmith–Sorkin conjectures.

This chapter discusses a general method for approximating marginals of large graphical models. This powerful technique has been discovered independently in various fields: statistical physics (under the name ‘Bethe Peierls approximation’), coding theory (‘sum-product’ and ‘min-sum’ algorithms), and artificial intelligence (‘belief propagation’). It is based on an exchange of messages between variables and factors, along the edges of the factor graph. These messages are interpreted as probability distributions for the variable in a graph where a cavity has been dug. The chapter also discusses the statistical analysis of these messages in large random graphical models: density evolution and the replica symmetric cavity method.

The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.

This chapter discusses the random regular k-SAT problem, i.e., a random k-CNF formula Φ‎ = Φ‎_k(n,d) on n variables such that each of the 2n literals appears exactly d times. With k₀ a certain constant, for any k > k₀ a number d_k is identified such that for any d ≤ d_k the random formula Φ‎ admits a truth assignment that satisfies all but o(n) clauses with high probability, whereas for d > d_k there is with high probability no such truth assignment. This phase transition is consistent with predictions based on the cavity method from statistical mechanics, and the proof also directly employs ideas from the cavity method, such as the notion of covers (relaxed satisfying assignments), which are obtained here via a whitening process.