caa a22 4500 467891230 CHVBK 20180406152750.0 cr unu---uuuuu 170328e20060901xx s 000 0 eng 10.1007/s10955-006-9162-3 doi (NATIONALLICENCE)springer-10.1007/s10955-006-9162-3 Reconstruction on Trees and Spin Glass Transition [Elektronische Daten] [Marc Mézard, Andrea Montanari] 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. Springer Science + Business Media, Inc., 2006 reconstruction nationallicence spin glasses nationallicence reconstruction threshold nationallicence phase transition nationallicence Mézard Marc Laboratoire de Physique Théorique et Modèles Statistiques, Université de Paris-Sud, bâtiment 100, 91405, Orsay Cedex, France aut Montanari Andrea Laboratoire de Physique Théorique de l'Ecole Normale Supérieure, 24 rue Lhomond 75231, Paris Cedex 05, France aut Journal of Statistical Physics Kluwer Academic Publishers-Plenum Publishers; http://www.springer-ny.com 124/6(2006-09-01), 1317-1350 0022-4715 124:6<1317 2006 124 10955 https://doi.org/10.1007/s10955-006-9162-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10955-006-9162-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mézard Marc Laboratoire de Physique Théorique et Modèles Statistiques, Université de Paris-Sud, bâtiment 100, 91405, Orsay Cedex, France aut NATIONALLICENCE 700 1- Montanari Andrea Laboratoire de Physique Théorique de l'Ecole Normale Supérieure, 24 rue Lhomond 75231, Paris Cedex 05, France aut NATIONALLICENCE 773 0- Journal of Statistical Physics Kluwer Academic Publishers-Plenum Publishers; http://www.springer-ny.com 124/6(2006-09-01), 1317-1350 0022-4715 124:6<1317 2006 124 10955 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer