Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2005-12-14
J. Stat. Phys. 124 (2006), 1317-1350
Physics
Condensed Matter
Statistical Mechanics
34 pages, 16 eps figures
Scientific paper
10.1007/s10955-006-9162-3
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.
Mezard Marc
Montanari Andrea
No associations
LandOfFree
Reconstruction on trees and spin glass transition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Reconstruction on trees and spin glass transition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction on trees and spin glass transition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-81154