Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm

Abstract

We study the Ising spin glass on random graphs with fixed connectivity z and with a Gaussian distribution of the couplings, with mean μand unit variance. We compute exact ground states by using a sophisticated branch-and-cut method for z=4,6 and system sizes up to N=1280 for different values of μ. We locate the spin-glass/ferromagnet phase transition at μ= 0.77 +/- 0.02 (z=4) and μ= 0.56 +/- 0.02 (z=6). We also compute the energy and magnetization in the Bethe-Peierls approximation with a stochastic method, and estimate the magnitude of replica symmetry breaking corrections. Near the phase transition, we observe a sharp change of the median running time of our implementation of the algorithm, consistent with a change from a polynomial dependence on the system size, deep in the ferromagnetic phase, to slower than polynomial in the spin-glass phase.

arXiv comment10 pages, RevTex, 10 eps figures. Some changes in the text

References in corpus (13)

• The Bethe lattice spin glass revisited
• A New Approach to Spin Glass Simulations
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• Phase Transition in the Number Partitioning Problem
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Scaling of stiffness energy for 3d +/-J Ising spin glasses
• Triviality of the Ground State Structure in Ising Spin Glasses
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Renormalization for Discrete Optimization
• Large-Scale, Low-Energy Excitations in the Two-Dimensional Ising Spin Glass
• Critical slowing down in polynomial time algorithms
• Numerical Results for Ground States of Spin Glasses on Bethe Lattices

Cited by in corpus (15)

• Critical phenomena in complex networks
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Universality-class dependence of energy distributions in spin glasses
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Large Deviations of the Free-Energy in Diluted Mean-Field Spin-Glass
• Zero-temperature spinglass-ferromagnetic transition : scaling analysis of the domain-wall energy
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• Genetic embedded matching approach to ground states in continuous-spin systems
• Unlearnable Games and "Satisficing'' Decisions: A Simple Model for a Complex World
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Quantum wavefunction annealing of spin glasses
• Ground-state magnetization of the Ising spin glass: A recursive numerical method and Chen-Ma scaling
• Numerical study of ground state energy fluctuations in spin glasses
• Configuration Memory in Patchwork Dynamics for Low-dimensional Spin Glasses
• Statistical properties of 1D spin glasses from first principles of classical mechanics