Information-theoretic thresholds from the cavity method (Q1649349): Difference between revisions

In this excellent paper, the authors give general exact formulas for the mutual information in an inference problem such as the stochastic block model or the low density generator matrix model. The authors then prove the existence of an information-theoretic threshold that connects the statistical inference problem with the condensation phase transition. They study the exact condensation phase transition in the Potts antiferromagnet on the random graph, thereby improving prior approximate results of \textit{P. Contucci} et al. [Commun. Math. Phys. 323, No. 2, 517--554 (2013; Zbl 1285.82007)]. Taking the cavity method into account, the authors reduce a combinatorial problem on a random graph to an optimization problem on the space of probability distributions on a simplex of bounded dimension. The authors prove the conjecture from \textit{F. Krząkała} et al. [Proc. Natl. Acad. Sci. USA 104, No. 25, 10318--10323 (2007; Zbl 1190.68031)] about the condensation phase transition in the random graph coloring problem for any number \(q\geq 3\) of colors. They then give four concrete applications that have each received considerable attention in their own right. Therefore, I think this article will be of great interest to scientists working on the field.