Reconstruction on trees and spin glass transition

Abstract

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.

34 pages, 16 eps figures

References in corpus (7)

• Phase transitions in an exactly soluble one-dimensional exclusion process
• The totally asymmetric exclusion process with extended objects, a model for protein synthesis
• Clustered bottlenecks in mRNA translation and protein synthesis
• Exact Results for the Asymmetric Simple Exclusion Process with a Blockage
• Local Inhomogeneity in Asymmetric Simple Exclusion Processes with Extended Objects
• Disordered asymmetric simple exclusion process: mean-field treatment
• Queuing Transitions in the Asymmetric Simple Exclusion Process

Cited by in corpus (78)

• Theoretical perspective on the glass transition and amorphous materials
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• Thermodynamic signature of growing amorphous order in glass-forming liquids
• Phase Transitions in the Coloring of Random Graphs
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hopping and the Stokes-Einstein relation breakdown in simple glass formers
• On the freezing of variables in random constraint satisfaction problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• The Static Lengthscale Characterizing the Glass Transition at Lower Temperatures
• Comparison of Static Length-Scales Characterizing the Glass Transition
• Particle jumps in structural glasses
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Constraint satisfaction problems with isolated solutions are hard
• Mode-Coupling as a Landau Theory of the Glass Transition
• Can the glass transition be explained without a growing static length scale?
• Reconstruction of Random Colourings
• Dynamic relaxation of a liquid cavity under amorphous boundary conditions
• Community detection in networks with unequal groups
• Typology of phase transitions in Bayesian inference problems
• Minimal contagious sets in random regular graphs
• Statistical Mechanics of the Minimum Dominating Set Problem
• Potts Glass on Random Graphs
• Mode-coupling theory predictions for the dynamical transitions of the partly pinned fluid systems
• Quiet Planting in the Locked Constraint Satisfaction Problems
• On the uniqueness of Gibbs measure in the Potts model on a Cayley tree with external field
• A Lattice Model for Colloidal Gels and Glasses
• Measurement-induced phase transitions on dynamical quantum trees
• Correlations of single-cell division times with and without periodic forcing
• Dynamical Heterogeneity in Lattice Glass Models
• Charting the replica symmetric phase
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Statistical Mechanics of maximal independent sets
• The cavity method for quantum disordered systems: from transverse random field ferromagnets to directed polymers in random media
• Confinement as a tool to probe amorphous order
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Biased landscapes for random Constraint Satisfaction Problems
• On the correspondence between thermodynamics and inference
• Phase transitions in the $q$-coloring of random hypergraphs
• The large deviations of the whitening process in random constraint satisfaction problems
• Broadcasting on Random Directed Acyclic Graphs
• On the solution of a `solvable' model of an ideal glass of hard spheres displaying a jamming transition
• Clustering from Sparse Pairwise Measurements
• Computing with Noise - Phase Transitions in Boolean Formulas
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Simple physics of the partly pinned fluid systems
• Numerical simulations of liquids with amorphous boundary conditions
• Complex Replica Zeros of $\pm J$ Ising Spin Glass at Zero Temperature
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Multi-body quenched disordered $XY$ and $p$-clock models on random graphs
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Spin glass phase transitions in the random feedback vertex set problem
• The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations
• Large Degree Asymptotics and the Reconstruction Threshold of the Asymmetric Binary Channels
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Broadcasting on Two-Dimensional Regular Grids
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• On the behaviour of random K-SAT on trees
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• Dynamically generated concatenated codes and their phase diagrams
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Statistical Physics of Medical Diagnostics: Study of a Probabilistic Model
• A discrete model of water with two distinct glassy phases
• Big Data Information Reconstruction on an Infinite Tree for a $4\times 4$-state Asymmetric Model with Community Effects
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• An alternate view of complexity in k-SAT problems
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Replica analysis of Franz-Parisi potential for sparse systems