Information-theoretic thresholds from the cavity method
Preprint
Abstract
Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs and we show that the mutual information holds the key to understanding certain important phase transitions in random graph models. We work out several concrete applications of these general results. For instance, we pinpoint the exact condensation phase transition in the Potts antiferromagnet on the random graph, thereby improving prior approximate results [Contucci et al.: Communications in Mathematical Physics 2013]. Further, we prove the conjecture from [Krzakala et al.: PNAS 2007] about the condensation phase transition in the random graph coloring problem for any number $q\geq3$ of colors. Moreover, we prove the conjecture on the information-theoretic threshold in the disassortative stochastic block model [Decelle et al.: Phys. Rev. E 2011]. Additionally, our general result implies the conjectured formula for the mutual information in Low-Density Generator Matrix codes [Montanari: IEEE Transactions on Information Theory 2005].
Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- Harnessing the Bethe free energyRandom Structures & Algorithms, 2016
- Satisfiability Threshold for Random Regular nae-satCommunications in Mathematical Physics, 2015
- The Condensation Phase Transition in Random Graph ColoringCommunications in Mathematical Physics, 2015
- The Replica Symmetric Solution for Potts Models on d-Regular GraphsCommunications in Mathematical Physics, 2014
- Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration2013
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007
- Bounds for diluted mean-fields spin glass modelsProbability Theory and Related Fields, 2004
- Broken Replica Symmetry Bounds in the Mean Field Spin Glass ModelCommunications in Mathematical Physics, 2003
- The Bethe lattice spin glass revisitedThe European Physical Journal B, 2001
- The concentration of the chromatic number of random graphsCombinatorica, 1997