Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses

Abstract

In a finite-connectivity spin-glass at the zero-temperature limit, long-range correlations exist among the unfrozen vertices (whose spin values being non-fixed). Such long-range frustrations are partially removed through the first-step replica-symmetry-broken (1RSB) cavity theory, but residual long-range frustrations may still persist in this mean-field solution. By way of population dynamics, here we perform a perturbation-percolation analysis to calculate the magnitude of long-range frustrations in the 1RSB solution of a given spin-glass system. We study two well-studied model systems, the minimal vertex-cover problem and the maximal 2-satisfiability problem. This work points to a possible way of improving the zero-temperature 1RSB mean-field theory of spin-glasses.

5 pages, two figures. To be published in JSTAT

References in corpus (15)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Loop series for discrete statistical models on graphs
• Glass models on Bethe lattices
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Loop Calculus in Statistical Physics and Information Science
• How to Compute Loop Corrections to Bethe Approximation
• Message passing for vertex covers
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Loop expansion around the Bethe-Peierls approximation for lattice models
• Statistical mechanics of the vertex-cover problem
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach

Cited by in corpus (4)

• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics