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

About 1 year old · traced to

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

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.