Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs. In such applications, variables are fixed sequentially to satisfy the constraints. Message passing is run after e
ach step. Its outcome provides an heuristic to make choices at next step. This approach has been referred to as `decimation, with reference to analogous procedures in statistical physics. The behavior of decimation procedures is poorly understood. Here we consider a simple randomized decimation algorithm based on belief propagation (BP), and analyze its behavior on random k-satisfiability formulae. In particular, we propose a tree model for its analysis and we conjecture that it provides asymptotically exact predictions in the limit of large instances. This conjecture is confirmed by numerical simulations.
Approximating marginals of a graphical model is one of the fundamental problems in the theory of networks. In a recent paper a method was shown to construct a variational free energy such that the linear response estimates, and maximum entropy estima
tes (for beliefs) are in agreement, with implications for direct and inverse Ising problems[1]. In this paper we demonstrate an extension of that method, incorporating new information from the response matrix, and we recover the adaptive-TAP equations as the first order approximation[2]. The method is flexible with respect to applications of the cluster variational method, special cases of this method include Naive Mean Field (NMF) and Bethe. We demonstrate that the new framework improves estimation of marginals by orders of magnitude over standard implementations in the weak coupling limit. Beyond the weakly coupled regime we show there is an improvement in a model where the NMF and Bethe approximations are known to be poor for reasons of frustration and short loops.
We analyze Mode Coupling discontinuous transition in the limit of vanishing discontinuity, approaching the so called $A_3$ point. In these conditions structural relaxation and fluctuations appear to have universal form independent from the details of
the system. The analysis of this limiting case suggests new ways for looking at the Mode Coupling equations in the general case.
We study link-diluted $pm J$ Ising spin glass models on the hierarchical lattice and on a three-dimensional lattice close to the percolation threshold. We show that previously computed zero temperature fixed points are unstable with respect to temper
ature perturbations and do not belong to any critical line in the dilution-temperature plane. We discuss implications of the presence of such spurious unstable fixed points on the use of optimization algorithms, and we show how entropic effects should be taken into account to obtain the right physical behavior and critical points.
We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substanti
ally this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second `condensation phase transition in the structure of the solution set for k larger or equal than 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m=1 via a correspondence with the tree reconstruction problem) and new large-k expansions.
In this paper we study finite interaction range corrections to the mosaic picture of the glass transition as emerges from the study of the Kac limit of large interaction range for disordered models. To this aim we consider point to set correlation fu
nctions, or overlaps, in a one dimensional random energy model as a function of the range of interaction. In the Kac limit, the mosaic length defines a sharp first order transition separating a high overlap phase from a low overlap one. Correspondingly we find that overlap curves as a function of the window size and different finite interaction ranges cross roughly at the mosaic lenght. Nonetheless we find very slow convergence to the Kac limit and we discuss why this could be a problem for measuring the mosaic lenght in realistic models.
