The cavity method at zero temperature

Abstract

In this note we explain the use of the cavity method directly at zero temperature, in the case of the spin glass on a Bethe lattice. The computation is done explicitly in the formalism equivalent to 'one step replica symmetry breaking'; we compute the energy of the global ground state, as well as the complexity of equilibrium states at a given energy. Full results are presented for a Bethe lattice with connectivity equal to three.

22 pages, 8 figures; Some minor corrections

Cited by in corpus (30)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Statistical physics of inference: Thresholds and algorithms
• Information-theoretic thresholds from the cavity method
• Replica bounds for diluted non-Poissonian spin systems
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• The Phase Diagram of 1-in-3 Satisfiability Problem
• The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective
• Charting the replica symmetric phase
• Numerical Results for Ground States of Spin Glasses on Bethe Lattices
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• Near optimal configurations in mean field disordered systems
• The large deviations of the whitening process in random constraint satisfaction problems
• Belief propagation for graph partitioning
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• The marginally stable Bethe lattice spin glass revisited
• The edge-disjoint path problem on random graphs by message-passing
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Properties of atypical graphs from negative complexities
• The full replica symmetry breaking in the Ising spin glass on random regular graph
• Metastable configurations on the Bethe lattice
• Statistical mechanics of budget-constrained auctions
• Near-power-law temperature dependence of the superfluid stiffness in strongly disordered superconductors
• Statistical analysis of edges and bredges in configuration model networks
• Scalable Node-Disjoint and Edge-Disjoint Multi-wavelength Routing
• An improved Belief Propagation algorithm finds many Bethe states in the random field Ising model on random graphs
• Optimal flow through the disordered lattice
• Simplified derivations for high-dimensional convex learning problems
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression