{
  "id": "cond-mat/0103328",
  "version": "v2",
  "published": "2001-03-15T18:36:06.000Z",
  "updated": "2001-08-15T09:27:56.000Z",
  "title": "Exact solutions for diluted spin glasses and optimization problems",
  "authors": [
    "S. Franz",
    "M. Leone",
    "F. Ricci-Tersenghi",
    "R. Zecchina"
  ],
  "comment": "4 pages, 1 figure, accepted for publication in PRL",
  "journal": "Phys. Rev. Lett. 87 (2001) 127209",
  "doi": "10.1103/PhysRevLett.87.127209",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech",
    "cs.CC"
  ],
  "abstract": "We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking Ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same Ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p=3, \\gamma_d=0.818 and \\gamma_s=0.918 resp.), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds (\\gamma_c^{var}=4.396 and \\gamma_c^{var}=2.149 resp.).",
  "revisions": [
    {
      "version": "v2",
      "updated": "2001-08-15T09:27:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimization problems",
      "diluted spin glasses",
      "exact solutions",
      "connectivity",
      "one-step functional replica symmetry"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Physical Review Letters",
      "year": 2001,
      "month": "Sep",
      "volume": 87,
      "number": 12,
      "pages": 127209
    },
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2001PhRvL..87l7209F"
    }
  }
}