25 problems

Consider the random K-LSAT linear program with $n$ variables and $m$ constraints, with all auxiliary variables $\psi$ set to zero. Let $N(n,m)$ be the maximum cardinality of a feas…

Let $c^*_K$ be the constant introduced in the source's theorem for the optimal value ${\cal LP}(n,c)$ of the random K-LSAT linear program, and consider the corresponding feasibilit…

Let $N(n,m)$ be the maximum number of clauses that can be satisfied by one assignment of $n$ variables in a random K-SAT instance with $m$ clauses, and let $c^*_K$ be the threshold…

Monasson et al.'s mixed-SAT conjecture. For every $p\in[0,1]$ there exists a value $\alpha_\mathrm{sat}(2+p)>0$ such that, whenever $\alpha_2,\alpha_3>0$ satisfy…

Consider clusters of solutions of a given size in the symmetric binary perceptron, and compare the clusters described by the planting procedure with those described by the full sol…

For a random $d$-regular $k$-uniform hypergraph, let $d_\star(k)$ denote the explicit upper bound on the satisfiability, equivalently $2$-colorability, threshold established in the…

Let $[...$

Let $\textsc{NAE-SAT}$ be the constraint satisfaction model at constraint density $[...$

Sharp phase-transition conjecture. There exists a critical density $alpha_c(kappa)$ such that the event $S_alpha(kappa)nevarnothing$ undergoes a sharp phase transition as $alpha$ c…

Phase-transition hypothesis. The existence of the sharp satisfiability phase transition itself may be the primary cause of algorithmic hardness in random $K$-SAT.

Rescaled-measure convergence conjecture. The sequence of positive measures $x_nQ_n$ converges to a positive measure $\rho$ vaguely on $(-1,1)$.

$u$-function-perceptron contiguity conjecture. The random and planted ensembles are contiguous for all $0<K\le K^*$ and $\alpha\in(0,\alpha_c^u(K))$.

Frozen-1RSB conjecture. For every $K>0$ and every $\alpha\in(0,\alpha_c^r(K))$, there exists $d_{\mathrm{min}}>0$ such that, with high probability over the RBP instance, for almost…

For a random hypergraph colouring model, let the rigidity threshold be the edge-density threshold at which the solution space develops the rigidity phenomenon, and let the algorith…

Let $d_{\mathrm{cond}}$ be the condensation threshold, let $\mathrm{corr}(d)$ denote the correlation quantity used to define the reconstruction threshold, and let…

Let $d_{\mathrm{KS}}$ be the Kesten–Stigum bound for a random constraint satisfaction problem, and let $d_{\mathrm{cond}}$ be its condensation threshold. Kesten–Stigum tightness co…

Reconstruction–clustering threshold conjecture. The reconstruction threshold coincides with the clustering threshold.

Sharp phase transition conjecture. In random $k$-SAT and a wide variety of general constraint satisfaction problems, there is a sharp phase transition: a typical problem is satisfi…

One-step replica-symmetry-breaking free-energy conjecture. For $alpha\in(alpha_{\mathrm{cond}},alpha_{\mathrm{sat}})$, the free energy equals a one-step replica-symmetry-breaking v…

Exact satisfiability threshold conjecture. For each $k\geq 3$, there is an exact satisfiability threshold $alpha_{\mathrm{sat}}(k)$ such that, for $alpha<alpha_{\mathrm{sat}}(k)$,…

Let $X_r(n,cn)$ be the random linear equation system with $r\geq 3$, and let $c_r^*$ denote its clustering threshold. For sufficiently small $\delta>0$, set $c=c_r^*-n^{-\delta}$.…

Let $k\ge k_0$ and $\alpha_{\mathrm{lbd}}\le\alpha\le\alpha_{\mathrm{ubd}}$. Let $\bm{\Omega}$ denote the number of clusters of the random $k$-SAT solution space, and let…

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…