Metraipolis › archive › dc_783d9bcd0085

Single-Variable Connectivity in Random $k$-SAT — arXiv:2611.05981

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05981
License (as archived)
CC0-1.0
Archived
2026-11-05T18:31:35.551Z
SHA-256 of the archived text
28e976c20b7cc1e4a51a2a442358c6c963cf6cc6d3af84565cf98cfcb922a8c5
Stable URL of this page
https://metraipolis.com/documento/dc_783d9bcd0085

How to cite

Single-Variable Connectivity in Random $k$-SAT — arXiv:2611.05981 — arXiv (en), https://arxiv.org/abs/2611.05981 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_783d9bcd0085 (Metraipolis archive dc_783d9bcd0085, sha256 28e976c20b7cc1e4a51a2a442358c6c963cf6cc6d3af84565cf98cfcb922a8c5)
BibTeX
@misc{dc783d9bcd0085,
  title = {Single-Variable Connectivity in Random $k$-SAT — arXiv:2611.05981},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05981},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_783d9bcd0085; sha256 28e976c20b7cc1e4a51a2a442358c6c963cf6cc6d3af84565cf98cfcb922a8c5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05981. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity. $\textbf{Single-variable connectivity up to reconstruction.}$ At clause densities up to \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+\gamma_*-o_k(1)\bigr),\] a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using $O_k(n)$ single-variable flips that preserve satisfiability. Here $\gamma_*\approx0.871$ arises from a refined tree-reconstruction analysis. $\textbf{Settling the reconstruction threshold.}$ Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+\gamma_*+o_k(1)\bigr),\] below the classical cavity prediction with constant term $1+O(\ln\ln k/\ln k)$. $\textbf{Shattering before rigidity.}$ We locate the looseness--rigidity transition at a higher density, matching the classical cavity prediction for clustering: \[\frac{2^k}{k} \left(\ln k+\ln\ln k+1+\Theta\left(\frac{\ln\ln k}{\ln k}\right)\right).\] Below the transition, we establish a stronger form of looseness: any variable of a typical solution can be reversed by logarithmically many single-variable flips that preserve satisfiability. Above it, reversing most variables of a typical solution requires changing linearly many variables (rigidity). Yet throughout an interval between reconstruction and rigidity, the solution space already splits into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers (shattering), while logarithmic looseness persists.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.05981 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.025Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).