Information-theoretic thresholds from the cavity method
DOI10.1016/j.aim.2018.05.029zbMath1397.82013arXiv1611.00814WikidataQ59459996 ScholiaQ59459996MaRDI QIDQ1649349
Amin Coja-Oghlan, Will Perkins, Lenka Zdeborová, Florent Krzakala
Publication date: 5 July 2018
Published in: Advances in Mathematics, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.00814
phase transitions; random graphs; Gibbs measures; stochastic block model; cavity method; belief propagation; information theoretic thresholds; random graph coloring
05C80: Random graphs (graph-theoretic aspects)
82B26: Phase transitions (general) in equilibrium statistical mechanics
82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
05C15: Coloring of graphs and hypergraphs
82D40: Statistical mechanics of magnetic materials
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
