The threshold conjecture for distributions of reducible uniquely extendable constraints
The threshold conjecture for distributions of reducible uniquely extendable constraints
Let , and let be a distribution over the set of -ary uniquely extendable constraint functions. Suppose that, if , every function in is commutative and reducible, or, if , every function is commutative with symmetric . Let be the random -XORSAT threshold constant. Threshold conjecture. If admits no constant solutions, then is the satisfiability threshold, in terms of the density , of . This conjecture generalizes the fixed-constraint threshold result to random choices from a distribution of constraint functions.
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.