Near optimal configurations in mean field disordered systems

Abstract

We present a general technique to compute how the energy of a configuration varies as a function of its overlap with the ground state in the case of optimization problems. Our approach is based on a generalization of the cavity method to a system interacting with its ground state. With this technique we study the random matching problem as well as the mean field diluted spin glass. As a byproduct of this approach we calculate the de Almeida-Thouless transition line of the spin glass on a fixed connectivity random graph.

13 pages, 7 figures

References in corpus (21)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Few-Particle Effects in Semiconductor Quantum Dots: Observation of Multi-Charged-Excitons
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Coloring random graphs
• Nature of the Spin Glass State
• Polynomial iterative algorithms for coloring and analyzing random graphs
• The cavity method at zero temperature
• On the Effects of a Bulk Perturbation on the Ground State of 3D Ising Spin Glasses
• Large-Scale, Low-Energy Excitations in the Two-Dimensional Ising Spin Glass
• The secondary structure of RNA under tension
• Ising Spin Glasses in a Magnetic Field
• Scaling and Universality in Continuous Length Combinatorial Optimization
• Zero Temperature Properties of RNA Secondary Structures
• Comparing Mean Field and Euclidean Matching Problems
• On the finite size corrections to some random matching problems
• Approximate analysis of search algorithms with "physical" methods
• Non trivial overlap distributions at zero temperature
• Droplet Phenomenology and Mean Field in a Frustrated and Disordered System
• Neighborhood preferences in random matching problems
• Metastable configurations on the Bethe lattice

Cited by in corpus (20)

• Statistical physics of inference: Thresholds and algorithms
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
• Behavior of Ising Spin Glasses in a Magnetic Field
• Elusive Glassy Phase in the Random Field Ising Model
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
• Diluted Mean-Field Spin-Glass Models at Criticality
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• A numerical study of the overlap probability distribution and its sample-to-sample fluctuations in a mean-field model
• Random-field p-spin glass model on regular random graphs
• Distribution of partition function zeros of the $\pm J$ model on the Bethe lattice
• Finite size scaling of the de Almeida-Thouless instability in random sparse networks
• Replica Symmetry and Combinatorial Optimization
• Local excitations in mean field spin glasses
• Analytical solution to Heisenberg spin glass models on sparse random graphs and their de Almeida-Thouless line
• Spin-glass behaviour on random lattices
• Mean-field theory of vector spin models on networks with arbitrary degree distributions
• Replica analysis of Franz-Parisi potential for sparse systems
• Small Coupling Expansion for Multiple Sequence Alignment