{
  "id": "0911.4328",
  "version": "v3",
  "published": "2009-11-23T06:06:33.000Z",
  "updated": "2010-07-02T02:53:55.000Z",
  "title": "Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems",
  "authors": [
    "Haijun Zhou"
  ],
  "comment": "6 pages, 4 figures, final version as accepted by International Journal of Modern Physics B",
  "categories": [
    "cond-mat.dis-nn"
  ],
  "abstract": "Random constraint satisfaction problems are interesting model systems for spin-glasses and glassy dynamics studies. As the constraint density of such a system reaches certain threshold value, its solution space may split into extremely many clusters. In this paper we argue that this ergodicity-breaking transition is preceded by a homogeneity-breaking transition. For random K-SAT and K-XORSAT, we show that many solution communities start to form in the solution space as the constraint density reaches a critical value alpha_cm, with each community containing a set of solutions that are more similar with each other than with the outsider solutions. At alpha_cm the solution space is in a critical state. The connection of these results to the onset of dynamical heterogeneity in lattice glass models is discussed.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2010-07-02T02:53:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random constraint satisfaction problems",
      "solution space",
      "heterogeneity",
      "criticality",
      "glassy dynamics studies"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1142/S0217979210056013",
      "journal": "International Journal of Modern Physics B",
      "year": 2010,
      "volume": 24,
      "number": 18,
      "pages": 3479
    },
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010IJMPB..24.3479Z"
    }
  }
}