Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses

Abstract

A formalism capable of handling the first step of hierarchical replica symmetry breaking in finite-connectivity models is introduced. The emerging order parameter is claimed to be a probability distribution over the space of field distributions (or, equivalently magnetisation distributions) inside the cluster of states. The approach is shown to coincide with the previous works in the replica symmetric case and in the two limit cases m=0,1 where m is Parisi's break-point. As an application to the study of optimization problems, the ground-state properties of the random 3-Satisfiability problem are investigated and we present a first RSB solution improving replica symmetric results.

16 pages Revtex file, 1 figure; amended version with two new appendices; to be published in J.Phys.A

Cited by in corpus (85)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Spectra of Sparse Random Matrices
• A ferromagnet with a glass transition
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Exact solutions for diluted spin glasses and optimization problems
• A single defect approximation for localized states on random lattices
• Information-theoretic thresholds from the cavity method
• Entropies of complex networks with hierarchically constrained topologies
• Partitioning and modularity of graphs with arbitrary degree distribution
• The Dynamic Phase Transition for Decoding Algorithms
• How to Compute Loop Corrections to Bethe Approximation
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Tricritical Points in Random Combinatorics: the (2+p)-SAT case
• Finite Connectivity Attractor Neural Networks
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Replicated Transfer Matrix Analysis of Ising Spin Models on `Small World' Lattices
• Spin Glass Phase Transition on Scale-Free Networks
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Geometrical organization of solutions to random linear Boolean equations
• Relaxation in graph coloring and satisfiability problems
• Finitely connected vector spin systems with random matrix interactions
• Sparsely-spread CDMA - a statistical mechanics based analysis
• On the stochastic dynamics of disordered spin models
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Analytic solution of attractor neural networks on scale-free graphs
• Statistical mechanics of the vertex-cover problem
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Spectra of Modular and Small-World Matrices
• Gallager error correcting codes for binary asymmetric channels
• The Little-Hopfield model on a Random Graph
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
• Circuits in random graphs: from local trees to global loops
• Time scale separation and heterogeneous off-equilibrium dynamics in spin models over random graphs
• Replica Cluster Variational Method
• Finitely coordinated models for low-temperature phases of amorphous systems
• The phase diagram of Lévy spin glasses
• Replica analysis of overfitting in regression models for time-to-event data
• Competition between glassiness and order in a multi-spin glass
• Aging dynamics of heterogeneous spin models
• Spin models on random graphs with controlled topologies beyond degree constraints
• Dynamical replica analysis of processes on finitely connected random graphs II: Dynamics in the Griffiths phase of the diluted Ising ferromagnet
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Thermodynamics of the Lévy spin glass
• Replica theory for Levy spin glasses
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Metastable configurations of spin models on random graphs
• The T=0 random-field Ising model on a Bethe lattice with large coordination number: hysteresis and metastable states
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Phase transitions in the three-state Ising spin-glass model with finite connectivity
• Enhanced storage capacity with errors in scale-free Hopfield neural networks: an analytical study
• Diluted antiferromagnet in a ferromagnetic enviroment
• Exact and Approximate Solutions for the Dilute Ising Model
• Dynamic rewiring in small world networks
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
• Magnetization Densities as Replica Parameters: The Dilute Ferromagnet
• Geometrical Frustration and Cluster Spin Glass with Random Graphs
• Ising spin glass in a random network with a gaussian random field
• Persistent individual bias in a voter model with quenched disorder
• New Understanding of the Bethe Approximation and the Replica Method
• Typical Performance of Irregular Low-Density Generator-Matrix Codes for Lossy Compression
• Equilibrium properties of disordered spin models with two scale interactions
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Inverse transitions in a spin-glass model on a scale-free network
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Boolean decision problems with competing interactions on scale-free networks: Critical thermodynamics
• Phase diagram and metastability of the Ising model on two coupled networks
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• On composite systems of dilute and dense couplings
• Stability of the replica-symmetric saddle-point in general mean-field spin-glass models
• Typical case behaviour of spin systems in random graph and composite ensembles
• A simple one dimensional glassy Kac model
• Phase transitions in atypical systems induced by a condensation transition on graphs
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Statistical mechanics of LDPC codes on channels with memory
• Cluster structure of optimal solutions in bipartitioning of small worlds
• Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem
• Bipartitioning of directed and mixed random graphs
• Mean-field theory of vector spin models on networks with arbitrary degree distributions
• Spectra of Modular Random Graphs