The threshold conjecture for distributions of reducible uniquely extendable constraints

About 1 year old · traced to

Let k≥3k\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 k≥4k\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.

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.