Reconstruction on Trees and Spin Glass Transition

By M. M'ezard, Andrea Montanari. 2005

160 citations recorded by the source corpus.

Consider an information source generating a symbol at the root of a tree network whose links correspond to noisy communication channels, and broadcasting it through the network. We study the problem of reconstructing the transmitted symbol from the information received at the leaves. In the large system limit, reconstruction is possible when the channel noise is smaller than a threshold.We show that this threshold coincides with the dynamical (replica symmetry breaking) glass transition for an associated statistical physics problem. Motivated by this correspondence, we derive a variational principle which implies new rigorous bounds on the reconstruction threshold. Finally, we apply a standard numerical procedure used in statistical physics, to predict the reconstruction thresholds in various channels. In particular, we prove a bound on the reconstruction problem for the antiferromagnetic “Potts” channels, which implies, in the noiseless limit, new results on random proper colorings of infinite regular trees.This relation to the reconstruction problem also offers interesting perspective for putting on a clean mathematical basis the theory of glasses on random graphs.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/2c8e746d440b3ce824fe46b3da546f381c15dd93

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Thermodynamic signature of growing amorphous order in glass-forming liquids (2008, background): “Interestingly, in this scenario, all finite point static correlations remain featureless, whereas the point-to-set correlations [9, 25], captured by qc(R), grow.”
Rigorous Inequalities Between Length and Time Scales in Glassy Systems (2006, unknown): “|ε) ≤ ℓi(ε) ≤ ℓ (2) i (ε) , (16) ℓ (2) i (ε) ≤ ℓ (1) i (ε) ≤ ℓ (2) i (µ∗ε/2) , (17) ℓ (2) i (”
Theoretical perspective on the glass transition and amorphous materials (2010, background): “Recently, the so-called ‘pointto-set’ correlation lengthscale was defined both in the context of RFOT theory as a practical measure of the mosaic lengthscale (Bouchaud and Biroli, 2004), and in more general settings (Montanari and Semerjian, 2006b; Mézard and Montanari, 2006).”