The replica-symmetry-breaking transition conjecture for random uniquely extendable CSPs
The replica-symmetry-breaking transition conjecture for random uniquely extendable CSPs
Let be a distribution over and let be the associated random uniquely extendable constraint system. Suppose that either and is reducible, or and every function in is symmetric. Let . Replica-symmetry-breaking conjecture. Below the threshold, if , and is a uniform random solution while are independent uniform variables, then for all . Above the threshold, if and , where is the set of constant solutions of , then a uniform random solution does not satisfy property a.a.s. This conjectures a replica-symmetry-breaking, or condensation, transition at density .
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.