ﻻ يوجد ملخص باللغة العربية
Many inference problems, notably the stochastic block model (SBM) that generates a random graph with a hidden community structure, undergo phase transitions as a function of the signal-to-noise ratio, and can exhibit hard phases in which optimal inference is information-theoretically possible but computationally challenging. In this paper we refine this description by emphasizing the existence of more generic phase diagrams with a hybrid-hard phase in which it is computationally easy to reach a non-trivial inference accuracy, but computationally hard to match the information theoretically optimal one. We support this discussion by quantitative expansions of the functional cavity equations that describe inference problems on sparse graphs. These expansions shed light on the existence of hybrid-hard phases, for a large class of planted constraint satisfaction problems, and on the question of the tightness of the Kesten-Stigum (KS) bound for the associated tree reconstruction problem. Our results show that the instability of the trivial fixed point is not a generic evidence for the Bayes-optimality of the message passing algorithms. We clarify in particular the status of the symmetric SBM with 4 communities and of the tree reconstruction of the associated Potts model: in the assortative (ferromagnetic) case the KS bound is always tight, whereas in the disassortative (antiferromagnetic) case we exhibit an explicit criterion involving the degree distribution that separates a large degree regime where the KS bound is tight and a low degree regime where it is not. We also investigate the SBM with 2 communities of different sizes, a.k.a. the asymmetric Ising model, and describe quantitatively its computational gap as a function of its asymmetry, and a version of the SBM with 2 groups of communities. We complement this study with numerical simulations of the Belief Propagation algorithm.
We experimentally address the importance of tuning in athermal phase transitions, which are triggered only by a slowly varying external field acting as tuning parameter. Using higher order statistics of fluctuations, a singular critical instability i
We review the information geometry of linear systems and its application to Bayesian inference, and the simplification available in the Kahler manifold case. We find conditions for the information geometry of linear systems to be Kahler, and the rela
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the spac
We study a random code ensemble with a hierarchical structure, which is closely related to the generalized random energy model with discrete energy values. Based on this correspondence, we analyze the hierarchical random code ensemble by using the re
We study in this paper the structure of solutions in the random hypergraph coloring problem and the phase transitions they undergo when the density of constraints is varied. Hypergraph coloring is a constraint satisfaction problem where each constrai