Reconstruction on trees and spin glass transition (Q858033)

The authors consider the following broadcast problem. An information source at the root of a tree network produces a letter (``color'') taken from a \(q\)-ary alphabet \(x \in \{1,\dots,q\}.\) The symbol is propagated along the edges of the tree. Each edge of the tree is an instance of the same noisy communication channel: if the letter \(x\) is transmitted through the channel, \(y\in \{1,\dots,q\}\) is received with probability \(\pi ( y | x).\) It is assumed that \(\pi (\cdot | \cdot)\) is irreducible and aperiodic. The problem of reconstruction: does the set all the symbols received at the vertices of the \(l\) the generation contain a non-vanishing information on the letter transmitted by the root, in the large \(l\) limit? The authors show that this threshold coincides with the dynamical glass transition for an associated physics problem. Motivated by this correspondence, a variational principle is derived which implies new rigorous bounds on the reconstruction threshold.