On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

Gino Del Ferraro*, Chuang Wang, Hai-Jun Zhou, Erik Aurell

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

We consider a one-step replica symmetry breaking description of the Edwards-Anderson spin glass model in 2D. The ingredients of this description are a Kikuchi approximation to the free energy and a second-level statistical model built on the extremal points of the Kikuchi approximation, which are also fixed points of a generalized belief propagation (GBP) scheme. We show that a generalized free energy can be constructed where these extremal points are exponentially weighted by their Kikuchi free energy and a Parisi parameter y, and that the Kikuchi approximation of this generalized free energy leads to second-level, one-step replica symmetry breaking (1RSB), GBP equations. We then proceed analogously to the Bethe approximation case for tree-like graphs, where it has been shown that 1RSB belief propagation equations admit a survey propagation solution. We discuss when and how the one-step-replica symmetry breaking GBP equations that we obtain also allow a simpler class of solutions which can be interpreted as a class of generalized survey propagation equations for the single instance graph case.

Original languageEnglish
Article number073305
Number of pages32
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2016
Issue number7
DOIs
Publication statusPublished - Jul 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • message-passing algorithms
  • optimization over networks
  • spin glasses (theory)
  • cavity and replica method
  • CLUSTER VARIATION METHOD
  • METASTABLE STATES
  • SATISFIABILITY
  • PROPAGATION
  • ALGORITHMS

Cite this