On the computational tractability of statistical estimation on amenable graphs

Ahmed El Alaoui, Andrea Montanari

We consider the problem of estimating a vector of discrete variables $({\theta }_1,\cdots ,{\theta }_n)$, based on noisy observations $Y_{uv}$ of the pairs $({\theta }_u,{\theta }_v)$ on the edges of a graph $G=([…