Abstract
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_{\ast}-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_{\ast}\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_{\ast}+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.
Chunyang Wang
Postdoc
I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.
Yitong Yin
Professor
I am a professor in the Theory Group at the School of Computer Science, Nanjing University. My research interests include randomized algorithms and computational sampling and counting, data structures and lower bounds, and parallel and distributed computing.
Yixiao Yu
Ph.D. Student
I am a fourth-year Ph.D. student in the Theory Group at Nanjing University, advised by Prof. Jingcheng Liu and Prof. Yitong Yin. My current research focuses on approximate sampling and counting.