The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels
Christian BorgsTheory Group, Microsoft Research Limited, UKJennifer ChayesTheory Group, Microsoft Research Limited, UKElchanan MosselDepartment of Statistics, University of California Berkeley, USASébastien RochDepartment of Statistics, University of California Berkeley, USA
2006en
ABI
Abstract
We establish the exact threshold for the reconstruction problem for a binary asymmetric channel on the b-ary tree, provided that the asymmetry is sufficiently small. This is the first exact reconstruction threshold obtained in roughly a decade. We discuss the implications of our result for Glauber dynamics, phylogenetic reconstruction, noisy communication and the so-called "replica symmetry breaking" in spin glasses and random satisfiability problems
Identifiers
Citations and references
Cited by 20 references