betaFeedback

WorksComputer Science

Single-Variable Connectivity in Random kk-SAT

Abstract

We resolve longstanding questions about connectivity, reconstruction,and looseness in random kk-SAT, for sufficiently large fixed kk as the number nn of variables tends to infinity. Single-variable connectivity up to reconstruction.\textbf{Single-variable connectivity up to reconstruction.} At clause densities up to 2kk(ln⁡k+ln⁡ln⁡k+γ∗−ok(1)),\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*-o_k(1)\bigr), a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using Ok(n)O_k(n) single-variable flips that preserve satisfiability. Here γ∗≈0.871γ_*\approx0.871 arises from a refined tree-reconstruction analysis. Settling the reconstruction threshold.\textbf{Settling the reconstruction threshold.} Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be 2kk(ln⁡k+ln⁡ln⁡k+γ∗+ok(1)),\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*+o_k(1)\bigr), below the classical cavity prediction with constant term 1+O(ln⁡ln⁡k/ln⁡k)1+O(\ln\ln k/\ln k). Shattering before rigidity.\textbf{Shattering before rigidity.} We locate the looseness–rigidity transition at a higher density, matching the classical cavity prediction for clustering: 2kk(ln⁡k+ln⁡ln⁡k+1+Θ(ln⁡ln⁡kln⁡k)).\frac{2^k}{k} \left(\ln k+\ln\ln k+1+Θ\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.

Introduction

Understanding how simple local constraints give rise to global structure and computational difficulty is a central challenge at the interface of theoretical computer science, probability, and statistical physics. Random constraint satisfaction problems bring these questions together in a common mathematical setting: as constraints accumulate, the space of solutions can change its organization before solutions disappear altogether. Random kk-SAT is a canonical model for studying these phenomena, connecting typical computational complexity with the phase transitions of disordered systems [MSL92, KS94, MZ96].

Two questions are central to this picture: when do satisfying assignments exist, and how accessible are they from one another through local updates? The first concerns the satisfiability threshold; the second matters for algorithms that explore the solution space.

The satisfiability threshold αsat\alpha_{\mathrm{sat}} illustrates the success of this interaction between physics and mathematics. For mm clauses on nn variables, write α=m/n\alpha= m/n for the clause density. Early experiments linked the cost of search to the transition [MSL92, KS94]. Friedgut [20] proved sharpness, and rigorous bounds [4] established the leading density 2kln⁡22^k \ln2. The cavity method predicted the precise limiting threshold [34, 31], established up to an additive ok(1)o_k(1) by Coja-Oghlan–Panagiotou [16] and exactly for all sufficiently large kk by Ding–Sly–Sun [19].

Moving between solutions may become difficult long before they disappear. Statistical physics predicts a sequence of transitions within the satisfiable phase [24 MRTS08]. We focus on the clustering, or dynamic, transition (αclust\alpha_{\mathrm{clust}} in Figure 1), at which solutions are predicted to organize into exponentially many groups.

Predicted phase diagram for random k-SAT at large k

Figure 1. Predicted phase diagram for random kk-SAT at large kk, from [19 Figure 1], adapted there from [24]. We locate αclust\alpha_{\mathrm{clust}} under the reconstruction criterion in Theorem 1.2.

A central characterization of the predicted clustering transition is the onset of reconstruction: distant variable values in a uniformly sampled solution retain nonvanishing information about a typical variable beyond what the formula alone reveals [28, 24]. Under non-reconstruction, this extra information vanishes with distance. Locating this information transition rigorously is a key step toward understanding the predicted clustered phase.

This picture has also shaped algorithm design. The cavity method led to survey propagation, whose messages describe the competing groups of solutions [34, 8]. On the rigorous side, Coja-Oghlan’s Fix algorithm finds a satisfying assignment in polynomial time up to (1−ok(1))2kln⁡k/k(1-o_k(1))2^k \ln k/k, the leading predicted clustering scale [15]. Low-degree polynomial algorithms face a provable obstruction at a constant multiple of this density [7].

Krzakala et al. [24] asked to determine this reconstruction threshold rigorously. The predicted reconstruction threshold is expressed on the large-kk density scale

α=2kk(ln⁡k+ln⁡ln⁡k+c).(1)\alpha= \frac{2^k}{k}\left(\ln k + \ln\ln k + c\right). \tag*{(1)}

Classical cavity calculations predicted c=1+O(ln⁡ln⁡k/ln⁡k)c = 1+O(\ln\ln k/\ln k) for random SAT [24 MRTS08]. A later heuristic tree-reconstruction analysis by Budzynski–Semerjian [9] predicted the smaller constant γ∗≈0.871\gamma_* \approx0.871 for graph coloring, leaving the corresponding SAT calculation open. Chen–Lonkar–Wang–Yang–Yin [12] proved non-reconstruction for finite random SAT formulas up to 2k/poly⁡(k)2^k/\operatorname{poly}(k), far below this scale.

The geometric picture concerns both global connectivity and local freedom. Connectivity asks whether almost all solutions can be joined by small satisfying moves; shattering partitions the solution space into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers. For a typical solution, sampled uniformly from the satisfying assignments of the given formula, looseness asks whether any variable can be reversed in a nearby satisfying assignment, without requiring a satisfying path (logarithmic looseness means Hamming distance Ok(ln⁡n)O_k(\ln n)); a variable is rigid if every satisfying assignment reversing its value lies at linear Hamming distance from the original solution.

The prediction of a dominant connected phase dates back to early cavity studies [MZ02]. Later accounts describe almost all solutions as connected by single-variable flips below the clustering transition [2 Zho10]. Rigorous results established separation and rigidity [30, 5, 1], but positive connectivity guarantees remained incomplete. Below (1−ok(1))2kln⁡k/k(1-o_k(1))2^k\ln k/k, Achlioptas–Coja-Oghlan [1 Conjecture 1] conjectured that every variable of a typical solution can be reversed by changing o(n)o(n) variables. Chen–Mani–Moitra [13 Conjectures 1.8 and 1.9] conjectured logarithmic looseness and connectivity among almost all solutions using moves changing Ok(ln⁡n)O_k(\ln n) variables. Near this scale, logarithmic looseness was proved for 99% of variables [18]; for every variable, only at lower densities [12], while connectivity was proved at exponentially smaller densities [13, 11].

These conjectures leave open the finer density bounds and whether single-variable flips suffice. More broadly, the central question is:

How does reconstruction relate to global connectivity and local freedom in the solution space?

Main results

We resolve the connectivity and looseness conjectures and determine the reconstruction threshold.

Single-variable connectivity up to reconstruction. Single-variable flips, the smallest possible moves, connect almost all solutions up to the asymptotic reconstruction threshold while preserving satisfiability throughout. A polynomial-time algorithm connects a typical pair in Ok(n)O_k(n) flips.

Settling the reconstruction threshold. Reconstruction begins at c=γ∗+ok(1)c = \gamma_* + o_k(1), below the classical prediction c=1+O(ln⁡ln⁡k/ln⁡k)c = 1+O(\ln\ln k/\ln k) and matching the refined constant predicted for colorings.

Shattering before rigidity. We locate the looseness–rigidity transition at c=1+Θ(ln⁡ln⁡k/ln⁡k)c = 1+\Theta(\ln\ln k/\ln k). Below it, any variable of a typical solution is reversible in Ok(ln⁡n)O_k(\ln n) satisfying single-variable flips; above it, most variables are rigid. Yet for 0.9615≤c<10.9615 \le c < 1, shattering with linear energy barriers coexists with looseness, realizing the predicted clustered but unfrozen regime [Sem08, MRTS08].

Model and conventions. The formula Φ=Φ(k,n,m)\Phi=\Phi(k,n,m) has mm independent clauses on [n][n]. Each chooses a uniform kk-element variable set and independent fair literal signs; complete clauses may repeat. Write α=m/n\alpha=m/n. The mass of a set of solutions is its fraction of all solutions.

A satisfying path is a sequence of satisfying assignments in which consecutive assignments differ at one variable; its length is the number of flips. All logarithms are natural. All results fix sufficiently large kk and then sufficiently large nn, uniformly over the stated density range.

Algorithmic single-variable connectivity. The constant γ∗≈0.871\gamma_* \approx0.871, numerically estimated in [9], is defined in (17) as the critical value of a refined tree-reconstruction recursion.

Theorem 1.1 (Algorithmic single-variable connectivity). There is a randomized polynomial-time algorithm such that, if

0≤α≤2kk(ln⁡k+ln⁡ln⁡k+γ∗−1(ln⁡ln⁡k)1/16),(2)0 \le\alpha\le\frac{2^k}{k}\left(\ln k+\ln\ln k+\gamma_*-\frac{1}{(\ln\ln k)^{1/16}}\right), \tag*{(2)}

then with probability at least 1−1/n1-1/n over Φ\Phi, the formula is satisfiable and the algorithm joins two supplied independent uniform solutions by a satisfying path of Ok(n)O_k(n) single-variable flips, with conditional success probability at least 1−1/n1-1/n over the endpoints and its random bits.

Consequently, on the same event, a giant component contains a set of mass at least 1−1/n1-1/n whose members can be joined within the set by Ok(n)O_k(n) satisfying single-variable flips.

The algorithm has an absolute polynomial exponent and always returns a verified path or failure. Averaging over the first endpoint gives a solution xx such that the solutions within L=Ok(n)L=O_k(n) satisfying flips of xx have mass at least 1−1/n1-1/n. Joining shortest paths through xx connects any two of them within this set in at most 2L2L flips.

The clustering threshold under reconstruction. We determine the clustering threshold αclust(k)\alpha_{\mathrm{clust}}(k) under the reconstruction criterion as defined in [24, 36].

For satisfiable Φ\Phi, let μΦ\mu_\Phi be uniform on its satisfying assignments. Conditional on Φ\Phi, choose vv uniformly from [n][n] and independently sample σ∼μΦ\sigma\sim\mu_\Phi. Write σB\sigma_B for its restriction to B⊆[n]B\subseteq[n]. Let B‾r(v)\overline{B}_r(v) be the variables at distance at least rr from vv, where two variables are adjacent if they appear in a common clause. Write pv=μΦ(σv=1)p_v=\mu_\Phi(\sigma_v=1) and qv,r=μΦ(σv=1∣σB‾r(v))q_{v,r}=\mu_\Phi(\sigma_v=1\mid\sigma_{\overline{B}_r(v)}). On unsatisfiable formulas, we set both quantities and prediction errors to zero.

Non-reconstruction and reconstruction mean Rk(α)=0R_k(\alpha)=0 and Rk(α)>0R_k(\alpha)>0, respectively, where

Rk(α):=lim⁡r→∞lim sup⁡n→∞E[∣qv,r−pv∣].R_k(\alpha):=\lim_{r\to\infty}\limsup_{n\to\infty}\mathbb{E}[|q_{v,r}-p_v|].

Here and in the theorem below, expectations are over the random formula Φ=Φ(k,n,⌊αn⌋)\Phi=\Phi(k,n,\lfloor\alpha n\rfloor), the uniform variable vv, and the uniform solution σ∼μΦ\sigma\sim\mu_\Phi. The limits are taken with kk and α\alpha fixed, first n→∞n\to\infty, then r→∞r\to\infty. The formula is known in both marginals; only the sampled exterior is additional information.

Among densities at which Φ\Phi is satisfiable with high probability, define the clustering threshold as the first reconstruction onset:

αclust(k):=inf⁡{α:Rk(α)>0}.\alpha_{\mathrm{clust}}(k):=\inf\{\alpha:R_k(\alpha)>0\}.

This first-onset definition does not assume that reconstruction is monotone in the clause density.

Theorem 1.2 (Reconstruction onset). Non-reconstruction holds throughout (2). For every fixed ε>0\varepsilon>0 and all sufficiently large kk, reconstruction holds throughout

2kk(ln⁡k+ln⁡ln⁡k+γ∗+ε)≤α≤2k(ln⁡2−1ln⁡k).(3)\frac{2^k}{k}\left(\ln k+\ln\ln k+\gamma_*+\varepsilon\right)\le\alpha\le2^k\left(\ln2-\frac{1}{\ln k}\right). \tag*{(3)}

At each such density, for every fixed r≥1r\ge1, the formula and σB‾r(v)\sigma_{\overline{B}_r(v)} predict σv\sigma_v with expected error O(1/(kln⁡k))+on(1)O(1/(k\ln k))+o_n(1), where O(⋅)O(\cdot) hides an absolute constant. Consequently,

αclust(k)=2kk(ln⁡k+ln⁡ln⁡k+γ∗+ok(1)).(4)\alpha_{\mathrm{clust}}(k)=\frac{2^k}{k}\left(\ln k+\ln\ln k+\gamma_*+o_k(1)\right). \tag*{(4)}

Shattering before rigidity. We locate the looseness–rigidity transition at c=1+Θ(ln⁡ln⁡k/ln⁡k)c = 1 + \Theta(\ln\ln k / \ln k), matching the classical clustering prediction [24]. Local single-variable connectivity holds throughout the looseness range. Shattering nevertheless occurs below this transition.

Theorem 1.3 (Looseness–rigidity transition). For every sufficiently large kk, there exists n0(k)n_0(k) such that, for every n≥n0(k)n \ge n_0(k), the following hold on opposite sides of the two density bounds

2kk(ln⁡k+ln⁡ln⁡k+1+ln⁡ln⁡k+1/2ln⁡k±8(ln⁡ln⁡k)2(ln⁡k)2).(5)\frac{2^k}{k}\left(\ln k+\ln\ln k+1+\frac{\ln\ln k+1/2}{\ln k}\pm\frac{8(\ln\ln k)^2}{(\ln k)^2}\right). \tag*{(5)}

In each density range below, with probability at least 1−1/n1-1/n over Φ\Phi, the formula is satisfiable and the corresponding conclusions hold.

(a) (Looseness) Up to the lower bound, a deterministic Ok(n)O_k(n)-time algorithm can reverse any requested variable of any of at least a 1−1/n1-1/n fraction of solutions along a satisfying path of at most 32(ln⁡k)5ln⁡n32(\ln k)^5\ln n flips.

(b) (Local connectivity) Under the same density bound and on the same event, each such solution can be connected to every solution in a Hamming ball of radius Θk(n)\Theta_k(n) around it by a satisfying path of length O(n)O(n), in deterministic Ok(n2)O_k(n^2) time.

(c) (Rigidity) From the upper bound up to 2k(ln⁡2−1/ln⁡k)2^k(\ln2-1/\ln k), all but an e−Ωk(n)e^{-\Omega_k(n)} fraction of solutions have (1−ok(1))n(1-o_k(1))n variables such that every satisfying assignment reversing any one of them differs from the original solution on Ωk(n)\Omega_k(n) variables.

References

  1. [1][AC08] Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793–802, 2008.
  2. [2][Ach09] Dimitris Achlioptas. Random satisfiability. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, chapter 8, pages 245–270. IOS Press, 2009.
  3. [3][ACRT11] Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Structures & Algorithms, 38(3):251–268, 2011.
  4. [4][AP04] Dimitris Achlioptas and Yuval Peres. The threshold for random k-SAT is 2^k log 2−O(k). Journal of the American Mathematical Society, 17(4):947–973, 2004.
  5. [5][ART06] Dimitris Achlioptas and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 130–139, 2006.
  6. [6][Bd16] Anton Bovier and Frank den Hollander. Metastability: A Potential-Theoretic Approach, volume 351 of Grundlehren der mathematischen Wissenschaften. Springer, 2016.
  7. [7][BH22] Guy Bresler and Brice Huang. The algorithmic phase transition of random k-SAT for low degree polynomials. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 298–309. IEEE, 2022.arxiv.org/abs/2106.02129
  8. [8][BMZ05] Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina. Survey propagation: an algorithm for satisfiability. Random Structures & Algorithms, 27(2):201–226, 2005.DOI
  9. [9]Louise Budzynski and Guilhem Semerjian. The asymptotics of the clustering transition for random constraint satisfaction problems. Journal of Statistical Physics, 181(5):1490–1522, 2020.DOI
  10. [10]Arnab Chatterjee, Amin Coja-Oghlan, Catherine Greenhill, Vincent Pfenninger, Maurice Rolvien, Pavel Zakharov, and Kostas Zampetakis. The random k-SAT Gibbs uniqueness threshold revisited. Combinatorics, Probability and Computing, 35(4):433–485, 2026.arxiv.org/abs/2506.01359
  11. [11]Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Andrés Herrera-Poyatos, Nitya Mani, and Ankur Moitra. Fast sampling of satisfying assignments from random k-SAT with applications to connectivity. SIAM Journal on Discrete Mathematics, 38(4):2750–2811, 2024.
  12. [12]Zongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang, and Yitong Yin. Counting random k-SAT near the satisfiability threshold. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 867–878, 2025. Theorem references follow the numbering in arXiv:2411.02980v1.arxiv.org/abs/2411.02980
  13. [13]Zongchen Chen, Nitya Mani, and Ankur Moitra. From algorithms to connectivity and back: finding a giant component in random k-SAT. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3437–3470, 2023. Theorem and conjecture references follow the numbering in arXiv:2207.02841v2.arxiv.org/abs/2207.02841
  14. [14]Amin Coja-Oghlan, Noëla Müller, and Jean B. Ravelomanana. Belief propagation on the random k-SAT model. The Annals of Applied Probability, 32(5):3718–3796, 2022.
  15. [15]Amin Coja-Oghlan. A better algorithm for random k-SAT. SIAM Journal on Computing, 39(7):2823–2864, 2010.
  16. [16]Amin Coja-Oghlan and Konstantinos Panagiotou. The asymptotic k-SAT threshold. Advances in Mathematics, 288:985–1068, 2016.
  17. [17]Amin Coja-Oghlan and Will Perkins. Belief propagation on replica symmetric random factor graph models. Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions, 5(2):211–249, 2018.
  18. [18]Amin Coja-Oghlan and Angelica Y. Pachon-Pinzon. The decimation process in random k-SAT. SIAM Journal on Discrete Mathematics, 26(4):1471–1509, 2012.
  19. [19]Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. Annals of Mathematics, 196(1):1–388, 2022.
  20. [20]Ehud Friedgut. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American Mathematical Society, 12(4):1017–1054, 1999.DOI
  21. [21]Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, and Christos H. Papadimitriou. The connectivity of Boolean satisfiability: Computational and structural dichotomies. SIAM Journal on Computing, 38(6):2330–2355, 2009.
  22. [22]Antoine Gerschenfeld and Andrea Montanari. Reconstruction for models on random graphs. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 194–204. IEEE, 2007.
  23. [23]Bruce Hajek. Cooling schedules for optimal annealing. Mathematics of Operations Research, 13(2):311–329, 1988.
  24. [24]Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104(25):10318–10323, 2007.pubmed.ncbi.nlm.nih.gov/17567754
  25. [26]Günter Last and Mathew Penrose. Lectures on the Poisson Process. Cambridge University Press, 2018.DOI
  26. [27]Colin McDiarmid. On the method of bounded differences. In Johannes Siemons, editor, Surveys in Combinatorics, 1989, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989.DOI
  27. [28]Marc Mézard and Andrea Montanari. Reconstruction on trees and spin glass transition. Journal of Statistical Physics, 124(6):1317–1350, 2006.
  28. [29]Elitza Maneva, Elchanan Mossel, and Martin J. Wainwright. A new look at survey propagation and its generalizations. Journal of the ACM, 54(4):17, 2007.
  29. [30]Marc Mézard, Thierry Mora, and Riccardo Zecchina. Clustering of solutions in the random satisfiability problem. Physical Review Letters, 94(19):197205, 2005.pubmed.ncbi.nlm.nih.gov/16090207
  30. [31]Stephan Mertens, Marc Mézard, and Riccardo Zecchina. Threshold values of random K-SAT from the cavity method. Random Structures & Algorithms, 28(3):340–373, 2006.
  31. [32]Michael Molloy. Cores in random hypergraphs and Boolean formulas. Random Structures & Algorithms, 27(1):124–135, 2005.DOI
  32. [33]Andrea Montanari. Estimating random variables from random sparse observations. European Transactions on Telecommunications, 19(4):385–403, 2008.arxiv.org/abs/0709.0145
  33. [34]Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812–815, 2002.
  34. [35]Michael Molloy and Ricardo Restrepo. Frozen variables in random Boolean constraint satisfaction problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1306–1318, 2013.
  35. [36]Andrea Montanari, Ricardo Restrepo, and Prasad Tetali. Reconstruction and clustering in random constraint satisfaction problems. SIAM Journal on Discrete Mathematics, 25(2):771–808, 2011.arxiv.org/abs/0904.2751

Paper details

vlnc:W_nykrn8gu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents