Connamacher and Molloy's satisfiability-threshold conjecture for random uniquely extendable CSPs

From papers

Let kk\frac{}{} and rr be fixed integers with k3k\geq 3 and r2r\geq 2. Let dkd_k be the constant defined in the random kk-XORSAT satisfiability-threshold theorem. Let Φ\Phi be a random (k,r)(k,r)-UE-SAT instance with nn variables and mm kk-ary uniquely extendable constraints. Connamacher and Molloy's conjecture. For every ε>0\varepsilon>0, a.a.s. Φ\Phi is satisfiable if m<(dk/kε)nm<(d_k/k-\varepsilon)n, and a.a.s. Φ\Phi is unsatisfiable if m>(dk/k+ε)nm>(d_k/k+\varepsilon)n. This conjecture proposes that the random (k,r)(k,r)-UE-SAT threshold agrees with the random kk-XORSAT threshold.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pu Gao and Theodore Morrison, “The satisfiability threshold and solution space of random uniquely extendable constraint satisfaction problems”, arXiv:2512.13819 (2026).

Solutions 0

No solutions have been posted yet.