Reconstruction for models on random graphs

@misc{citeulike:1257891, abstract = {The reconstruction problem requires to estimate a random variable given `far away' observations. Several theoretical results (and simple algorithms) are available when the underlying probability distribution is Markov with respect to a tree. In this paper we estabilish several exact thresholds for loopy graphs. More precisely we consider models on random graphs that converge locally to trees. We establish the reconstruction thresholds for the Ising model both with attractive and random interactions (respectively, `ferromagnetic' and `spin glass'). Remarkably, in the first case the result does not coincide with the corresponding tree threshold. Among the other tools, we develop a sufficient condition for the tree and graph reconstruction problem to coincide. We apply such condition to antiferromagnetic colorings of random graphs.}, author = {Gerschenfeld, Antoine and Montanari, Andrea }, citeulike-article-id = {1257891}, eprint = {0704.3293}, keywords = {graph, random-graph, spin-glass, tree}, month = {Apr}, posted-at = {2007-04-26 21:29:28}, priority = {2}, title = {Reconstruction for models on random graphs}, url = {http://arxiv.org/abs/0704.3293}, year = {2007} }

TY - ELEC ID - citeulike:1257891 L3 - citeulike-article-id:1257891 TI - Reconstruction for models on random graphs N2 - The reconstruction problem requires to estimate a random variable given `far away' observations. Several theoretical results (and simple algorithms) are available when the underlying probability distribution is Markov with respect to a tree. In this paper we estabilish several exact thresholds for loopy graphs. More precisely we consider models on random graphs that converge locally to trees. We establish the reconstruction thresholds for the Ising model both with attractive and random interactions (respectively, `ferromagnetic' and `spin glass'). Remarkably, in the first case the result does not coincide with the corresponding tree threshold. Among the other tools, we develop a sufficient condition for the tree and graph reconstruction problem to coincide. We apply such condition to antiferromagnetic colorings of random graphs. KW - graph KW - random-graph KW - spin-glass KW - tree AU - Gerschenfeld, Antoine AU - Montanari, Andrea PY - 2007/Apr/25/ UR - http://arxiv.org/abs/0704.3293 ER -