The threshold conjecture for distributions of reducible uniquely extendable constraints

From papers

Let k3k\geq 3, and let μ\mu be a distribution over the set Λk,r\Lambda_{k,r} of kk-ary uniquely extendable constraint functions. Suppose that, if k4k\geq 4, every function in supp(μ)\operatorname{supp}(\mu) is commutative and reducible, or, if k=3k=3, every function ψsupp(μ)\psi\in\operatorname{supp}(\mu) is commutative with symmetric fψ(2)f_{\psi}^{(2)}. Let dkd_k be the random kk-XORSAT threshold constant. Threshold conjecture. If μ\mu admits no constant solutions, then dk/kd_k/k is the satisfiability threshold, in terms of the density d=m/nd=m/n, of Hn(μ,k,m)H_n(\mu,k,m). 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

No solutions have been posted yet.