14 problems

Let $V=\{v_1,\dots,v_n\}$, let $E$ be a sparse Erdős–Rényi $k$-uniform multi-hypergraph with $m$ edges, and let $\chi:\{0,1\}^k\to\{0,1\}$ be a Boolean predicate selected uniformly…

Let $\pi$ be a distribution over $\Lambda_{k,r}$ and let $H_n(\pi,k,m)$ be the associated random uniquely extendable constraint system. Suppose that either $k\geq 4$ and…

Let $\pi$ be a distribution over $\Lambda_{k,r}$, and let $H_n(\pi,k,m)$ be the associated random uniquely extendable constraint system. Weakened-support conjecture. Theorem should…

Let $G$ be a finite group of order at least two, and let $H_n(\pi,k,m)$ be the random uniquely extendable constraint system arising from the group-equation model described in the s…

Let $k\geq 3$, and let $\mu$ be a distribution over the set $\Lambda_{k,r}$ of $k$-ary uniquely extendable constraint functions. Suppose that, if $k\geq 4$, every function in…

Let $k\frac{}{}$ and $r$ be fixed integers with $k\geq 3$ and $r\geq 2$. Let $d_k$ be the constant defined in the random $k$-XORSAT satisfiability-threshold theorem. Let $\Phi$ be…

A random constraint satisfaction problem (CSP) is a random optimization problem whose solutions may undergo a shattering transition, at which the solution space changes from one la…

Krauth–Mézard and Huang et al.'s freezing conjecture. For the asymmetric binary perceptron, typical solutions belong to clusters of vanishing entropy density, and, more strongly, s…

Krauth–Mézard's sharp threshold conjecture. A sharp threshold occurs at $\alpha^*_{\kappa}$: for constraint densities below $\alpha^*_{\kappa}$, solutions exist with high probabili…

Let $\alpha_c$ be the critical density, and let $\mathbb{P}_{\mathrm r}$ and $\mathbb{P}_{\mathrm{pl}}$ denote respectively the random and planted models of the symmetric Ising per…

Consider successful learning algorithms for the Ising perceptron and the clusters containing the solutions they find. A cluster has positive entropy density when its size is expone…

Let the Ising perceptron have constraint density below its critical capacity. A cluster is a collection of solutions in the solution space. Krauth–Mézard's conjecture. At all densi…

Let random NAE-SAT be the constraint satisfaction problem in which each constraint contains $K$ random literals, and let bicoloring of random hypergraphs be the problem in which ea…

Let random graph coloring be the problem in which vertices are assigned colors and each edge forbids equal colors, and let the “permutated” version be the model in which every edge…