Generalization of the cavity method for adiabatic evolution of Gibbs states

Abstract

Mean field glassy systems have a complicated energy landscape and an enormous number of different Gibbs states. In this paper, we introduce a generalization of the cavity method in order to describe the adiabatic evolution of these glassy Gibbs states as an external parameter, such as the temperature, is tuned. We give a general derivation of the method and describe in details the solution of the resulting equations for the fully connected p-spin model, the XOR-SAT problem and the anti-ferromagnetic Potts glass (or "coloring" problem). As direct results of the states following method, we present a study of very slow Monte-Carlo annealings, the demonstration of the presence of temperature chaos in these systems, and the identification of a easy/hard transition for simulated annealing in constraint optimization problems. We also discuss the relation between our approach and the Franz-Parisi potential, as well as with the reconstruction problem on trees in computer science. A mapping between the states following method and the physics on the Nishimori line is also presented.

37 pages

References in corpus (17)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Jamming versus Glass Transitions
• A Landscape Analysis of Constraint Satisfaction Problems
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The critical behavior of three-dimensional Ising spin glass models
• On the freezing of variables in random constraint satisfaction problems
• Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Reconstruction of Random Colourings
• Potts Glass on Random Graphs
• Random subcubes as a toy model for constraint satisfaction problems
• Marginal States in Mean Field Glasses
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Off-equilibrium confined dynamics in a glassy system with level-crossing states

Cited by in corpus (3)

• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
• Replica symmetry breaking, complexity and spin representation in the generalized random energy model
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems