Family 235Probability and statistical mechanicsNo LeanNot yet digested
Limiting random SAT thresholds, sharp variance and computability
For random k-SAT with independent uniformly signed proper clauses sampled with replacement, proves finite positive limiting thresholds and hitting-time variance for every fixed k ≥ 3, and computability of the 3-SAT threshold. We credit Gaia Carenini with priority for resolving the threshold-existence conjecture in her concurrent ECCC TR26-229, made public October 5, 2026; this family supplies another proof and the sharper variance and computability results.
Manuscripts in this family · 4
A Limiting Satisfiability Threshold for Every Fixed Clause Size
Sep 25, 2026·article.pdf
For every fixed integer k ≥ 3, random k-SAT with independent uniformly signed clauses on distinct variables, sampled with replacement, has a finite positive limiting satisfiability threshold. We credit Gaia Carenini [[5]](https://eccc.weizmann.ac.il/report/2026/229/) with priority for resolving the satisfiability conjecture. This paper gives an alternative proof, using concentration of a capped last satisfiable index and a comparison between different system sizes.
Linear Variance of the Random 3-SAT Hitting Time
Oct 5, 2026·linear-variance-of-the-random-3-sat-hitting-time.pdf
For random 3-SAT on n Boolean variables, with independent uniformly signed clauses on three distinct variables sampled with replacement, we prove that the first unsatisfiable prefix has variance . The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.
Variance of the Random k-SAT Hitting Time
Sep 27, 2026·article.pdf
Let H be the index of the first unsatisfiable prefix in random k-SAT on n variables, with independent uniformly signed clauses using k distinct variables and sampled with replacement. For every fixed k ≥ 4, we prove . For k = 3, the variance is bounded below by a positive multiple of n and above by a constant multiple of ; the companion paper on random 3-SAT sharpens this to . The same upper bounds proved here hold after clipping at any fixed positive multiple of n.
Computing the Random 3-SAT Threshold
Sep 27, 2026·article.pdf
The limiting satisfiability threshold of uniform random 3-SAT is a computable real. We credit Gaia Carenini [[4]](https://eccc.weizmann.ac.il/report/2026/229/) with priority for resolving the satisfiability conjecture, which establishes the threshold's existence. We prove that one finite deterministic machine can approximate it to any prescribed accuracy. A deletion estimate gives explicit lower certificates, while a finite hierarchical approximation of the soft pressure gives upper certificates at every larger rational density. A fair search through these certificates halts without requiring a computable rate of finite-size convergence.