number of vertices approaches infinity.

By definition, maximum a posteriori (MAP) decoding always maximizes the probability of recovering the correct vertex-variables. Since we assume uniform priors, maximum likelihood (ML) and MAP decoding coincide. Hence, our definition of exact recovery is tantamount to requiring that ML decoding recovers the vertex-variables $x^V$ up to an unavoidable additive offset $\phi \in \left\{ 0^V, 1^V \right\}$ with some probability that converges to $1$ as the number of vertices approaches infinity. Note that an ML decoder produces vertex-variables $\tilde x^V$ that minimize the number of edges $(i,j)$ of $G$ for which $Y^E_{ij} \oplus \tilde x_i \oplus \tilde x_j$ is non-zero.

A Necessary Condition for Successful Recovery
---------------------------------------------

For each graph $G = \left( V, E \right)$ (drawn from the Erdős-Rényi model or not), the following result holds:

\[th:convKLDiv\] Let $0 < \tau < 2/3$ and let $d$ be the average degree of $G$. If $d \leq n^\tau$ then, recovery with high probability is possible only if - + o ( ).\[eq:convGenEps\] If $\varepsilon \rightarrow 1/2$, this condition implies 2 + o ( ). \[eq:convBigEps\]

Before proving this Theorem, we compare it with the necessary condition $
d \geq 2/(1 - H \! \left( \varepsilon \right) 