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

About 1 year old · traced to

Let kk\frac{}{} and rr be fixed integers with k≥3k\geq 3 and r≥2r\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.