3 problems

Let $r_{k\mathrm{-NAE}}$ denote the satisfiability threshold for random $k$-NAESAT, and let the Survey Propagation formalism produce its associated variational problem. SP variatio…

Let $\vec\Phi$ be a random $k$-NAESAT formula in the condensation phase, and let $\mathcal{S}(\vec\Phi)$ be its solution set. Partition $\mathcal{S}(\vec\Phi)$ into clusters, choos…

Let $r_{k\mathrm{-NAE}}$ denote the satisfiability threshold for random $k$-NAESAT instances. The asymptotic k-NAESAT threshold conjecture. … The source states that this conjecture…