{
  "id": "2309.09913",
  "version": "v1",
  "published": "2023-09-18T16:26:53.000Z",
  "updated": "2023-09-18T16:26:53.000Z",
  "title": "Sharp Phase Transition for Multi Overlap Gap Property in Ising $p$-Spin Glass and Random $k$-SAT Models",
  "authors": [
    "Eren C. Kızıldağ"
  ],
  "categories": [
    "math.PR",
    "cs.CC",
    "cs.DS",
    "math-ph",
    "math.MP"
  ],
  "abstract": "The Ising $p$-spin glass and the random $k$-SAT models exhibit symmetric multi Overlap Gap Property ($m$-OGP), an intricate geometrical property which is a rigorous barrier against many important classes of algorithms. We establish that for both models, the symmetric $m$-OGP undergoes a sharp phase transition and we identify the phase transition point for each model: for any $m\\in\\mathbb{N}$, there exists $\\gamma_m$ (depending on the model) such that the model exhibits $m$-OGP for $\\gamma>\\gamma_m$ and the $m$-OGP is provably absent for $\\gamma<\\gamma_m$, both with high probability, where $\\gamma$ is some natural parameter of the model. Our results for the Ising $p$-spin glass model are valid for all large enough $p$ that remain constant as the number $n$ of spins grows, $p=O(1)$; our results for the random $k$-SAT are valid for all $k$ that grow mildly in the number $n$ of Boolean variables, $k=\\Omega(\\ln n)$. To the best of our knowledge, these are the first sharp phase transition results regarding the $m$-OGP. Our proofs are based on an application of the second moment method combined with a concentration property regarding a suitable random variable. While a standard application of the second moment method fails, we circumvent this issue by leveraging an elegant argument of Frieze~\\cite{frieze1990independence} together with concentration.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-18T16:26:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "multi overlap gap property",
      "spin glass",
      "sat models",
      "sharp phase transition results",
      "second moment method"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}