11 problems

Let $\rho$) be the root of a tree, let $u$ denote the broadcast labeling on its vertices, and consider message-passing algorithms whose messages take values in an alphabet $\Sigma$…

Non-integer BP solution conjecture. The non-integer solution extends beyond the small $T_c+\varepsilon$ vicinity of $T_c$ and transitions smoothly as $T\to\infty$ into the fully ho…

Finite-termination conjecture. If $\pi^*$ is unique, then the min-sum auction I algorithm terminates after finitely many iterations when this condition is removed from step (4).

Unique-fixed-point conjecture. If $mu=nu$, then this recursion has a unique fixed point for every

For a counter-braid ensemble, let $\bar{\epsilon}$ denote the area threshold, namely the value at which the area under the relevant extended belief-propagation extrinsic informatio…

In the large-degree regime, let $\mu$ and $\alpha$ be the parameters appearing in the scalar density-evolution recursion, and let $h(v)$ be the function defined by that recursion.…

Under the binary symmetric stochastic block model with $\alpha$-noisy side information, let $p_{G_n}(\widehat{\sigma}_{\rm BP}^t)$ be the estimation accuracy of belief propagation a…

Sudderth–Wainwright–Willsky conjecture. If $f$ admits a pairwise, log-supermodular factorization over $G$, then

Let $p$ be a non-negative matrix, and let $Z_{o\text{-}f}^{(\gamma)}(p)$ denote the fractional BP partition-function estimate at parameter $\gamma$. In particular, write…

Gurvits's BP upper-bound conjecture. For any non-negative $p$, $f(n)$ is asymptotic to $\sqrt{2}^n$. This conjecture concerns the worst-case multiplicative gap between the permanen…

Let ${\mathcal{C}}$ be a code drawn from a sequence of “good” codes, and let ${\bf Y}_2$ be the channel output at the relay. Let ${\bf Y}^{\textrm{BP}}_2$ be the output of belief p…