Bounded-memory impossibility conjecture for belief propagation reconstruction

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$ with $|\Sigma|=L$, where $L>0$ is fixed. Reconstruction is the problem of estimating $u_\rho$ from the messages received at the root. Bounded-memory impossibility conjecture. For any fixed $L > 0$, no message-passing algorithm on an alphabet of size $L$ can achieve the guarantee of the Kesten–Stigum threshold. In other words, there \exists a fixed noise level $\varepsilon(L)$ such that reconstruction is information-theoretically possible but no such message-passing algorithm is asymptotically better than a random guess. This conjecture asserts that attaining the reconstruction threshold requires unbounded memory, ruling out any bounded-memory analogue of belief propagation.