The replica-symmetry-breaking transition conjecture for random uniquely extendable CSPs

From papers

Let π\pi be a distribution over Λk,r\Lambda_{k,r} and let Hn(π,k,m)H_n(\pi,k,m) be the associated random uniquely extendable constraint system. Suppose that either k4k\geq 4 and supp(π)\operatorname{supp}(\pi) is reducible, or k=3k=3 and every function in F2(supp(π))F_2(\operatorname{supp}(\pi)) is symmetric. Let ε>0\varepsilon>0. Replica-symmetry-breaking conjecture. Below the threshold, if m<(dk/kε)nm<(d_k/k-\varepsilon)n, and xx is a uniform random solution while u,vu,v are independent uniform variables, then P[xu=σ,xv=τ]=1/q2+o(1)\mathbb P[x_u=\sigma,x_v=\tau]=1/q^2+o(1) for all σ,τΩ\sigma,\tau\in\Omega. Above the threshold, if m>(dk/k+ε)nm>(d_k/k+\varepsilon)n and QψQ_\psi\neq\varnothing, where QψQ_\psi is the set of constant solutions of ψ\psi, then a uniform random solution does not satisfy property RS\mathrm{RS} a.a.s. This conjectures a replica-symmetry-breaking, or condensation, transition at density dkd_k.

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.