Connamacher and Molloy's satisfiability-threshold conjecture for random uniquely extendable CSPs
Connamacher and Molloy's satisfiability-threshold conjecture for random uniquely extendable CSPs
Let and be fixed integers with and . Let be the constant defined in the random -XORSAT satisfiability-threshold theorem. Let be a random -UE-SAT instance with variables and -ary uniquely extendable constraints. Connamacher and Molloy's conjecture. For every , a.a.s. is satisfiable if , and a.a.s. is unsatisfiable if . This conjecture proposes that the random -UE-SAT threshold agrees with the random -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
Sign in to submit a solution.
No solutions have been posted yet.