This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. It is accessible to graduate students and researchers without a specific training in any of these fields. The selected topics include spin glasses, error correcting codes, satisfiability, and are central to each field. The approach focuses on large random instances, adopting a common probabilistic formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to study phase transitions.

σi σj − B σi , (2.53) i∈L where the sum over (ij) runs over all the (unordered) couples of sites i, j ∈ L which are nearest neighbors. The real number B measures the applied external magnetic field. Determining the free energy density f (β) in the thermodynamic limit for this model is a non-trivial task. The model was invented by Wilhem Lenz in the early twenties, who assigned the task of analyzing it to his student Ernst Ising. In his dissertation thesis (1924) Ising solved the d = 1 case

block error probability: Pav B ≡ 1 2M Q(y|x) I(d(y) = x) x (3.4) y A simple decoding algorithm would be the following: for each received message y, consider all the 2N codewords, and determine the most likely one: d(y) = arg maxx Q(y|x). It is clear that this algorithm minimizes the average block error probability. For a general code, there is no better way for maximizing Q(y|x) than going through all codewords and computing their likelihood one by one. This takes a time of order 2M , which

2 [E N (ε, ε + δ)]2 (5.12) with B = supx∈[ε,ε+δ] sa (x) > 0. A slight variation of the above reasoning is often referred to as the second moment method, and will be further discussed in App. ????. Finally, the statement (5.10) follows from the previous estimates through a straightfoward application of Borel-Cantelli Lemma. Exercise 5.1 Large deviations: let Nout (δ) be the total number of configurations j such that |Ej | > N (ε∗ + δ), with δ > 0. Use Markov inequality to show that the fraction

played by Hamming distance; finally, the Gaussian distribution of the energy levels is replaced here by the binomial distribution). A pictorial interpretation of the above result is shown in Fig. 6.2 (notice that it is often misleading to interpret phenomena occurring in spaces with a large num- ‘‘Info Phys Comp’’ Draft: November 9, 2007 -- ‘‘Info Phys 110 RANDOM CODE ENSEMBLE codewords x (0) {fig:RCEHammingSpace} δ GV Fig. 6.2. A pictorial view of a typical code from the random code

incorrect codewords x(1) , . . . , x(2 −1) : (0) Z = e−2Bd(x N ,y) + d=0 Ny (d) e−2Bd ≡ Zcorr + Zerr , (6.16) where we denoted by Ny (d) the number of incorrect codewords at a distance d from the vector y. The contribution of x(0) in the above expression is easily estimated. By the central limit theorem d(x(0) , y) ≃ N p and therefore Zcorr is close to e−2N Bp with high probability. More precisely, for any ε > 0, e−N (2Bp+ε) ≤ Zcorr ≤ e−N (2Bp−ε) with probability approaching one in the N →