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 $\rho$ denote the clause density in a random $k$-SAT formula, let $\theta=1-t/n$ denote the time parameter of the decimation process, and let $\rho_0$ be a constant independent…