**Information theory has been closely related to concepts of statistical mechanics, almost from its inception. In recent years this connection has been extended to encompass: error correcting codes based on random graphs on one hand, and spin glasses on the other hand. In a nutshell, these systems display phase transitions of similar nature.**

**Phase transitions** are an ubiquitous natural phenomenon and occur in almost all physical situations involving a macroscopic number of interacting degrees of freedom. The most well known ones are displayed in the **phase diagram of ordinary matter** (left picture). The system undergoes sudden transitions between liquid and solid or liquid and vapour phases when the control parameters such as pressure and/or temperature cross the solid lines. Simple but very important

models which capture essential features of phase transitions belong to the class of **Ising spin systems** (right picture). Binary variables (also called spins) taking values `+1/-1`

, and representing the presence/absence of a water molecule are attached to the red circles of the lattice. The blue squares indicate that there is an energy cost depending on the pair `(+1,+1)`

`(+1,-1)`

`(-1,+1)`

`(-1,-1)`

joined by the edge. Each configuration of spins on the lattice is assigned a probability weight depending on the total energy cost. The main qualitative features of the water-vapour phase transition are captured by the typical configurations of the **Gibbs probability weight**.

**Modern error correcting codes** are also based on probabilistic graphical models.
For example, in **Low Density Parity Check Codes** (`LDPC`

) the code words are strings of bits (`1 and 0`

) attached to the red nodes, satisfying a set of linear constraints depicted by the graph below. All the bits that are connected to a square blue node (a parity check) sum to zero modulo `2`

.
The code words are sent through a communication channel which flips each bit with a certain probability `p`

(the noise level). As such, **the code bits can be viewed as set of interacting spins and the communication system can be modelled by a probabilistic graphical model belonging to the Ising class**. The system displays a phase transition between a phase `p<p_c`

where it

is in principle possible to clean the errors and reconstruct perfectly the original code word; and a phase `p>p_c`

where this is impossible. However for `p<p_c`

it is not always possible to perform the error correction by an efficient algorithm. It turns out that a fundamental **efficient algorithm**, called **belief propagation** and related to **mean field methods of statistical physics**, can efficiently correct the errors for `p<p_d`

. These phase transitions share deep similarities with the ones occuring in **spin glasses** which are spin systems based on **random Gibbs weights**. Indeed, the probabilistic models for graphical coding schemes have quenched randomness coming from the underlying graph code as well as the channel output realizations.