condition for the Erdős-Rényi graph match.[^7] Remarkably, the sufficient condition for the efficient SDP-based method to achieve exact recovery matches the IT bound up to a factor of $2$.

If the noise parameter $\varepsilon$ is bounded away from both zero and $1/2$, then all conditions imply $d = \Theta \! \left( \log \! \left( n \right) \right)$, where $d$ is the expected average degree: $d = pn$. The factors by which the bounds differ decrease with an increasing noise parameter $\varepsilon$. Since in the noise-free case exact recovery is possible if and only if the graph is connected, which is true for trees (with $d \leq 2$) and, for Erdős-Rényi graphs only when $d \geq \log \! \left( n \right)$, the factors between the necessary condition and the sufficient conditions necessarily approach infinity when $\varepsilon$ decreases to zero (since $D(1/2||{\varepsilon})$ diverges).

Information Theoretic Bounds
============================

This section presents necessary and sufficient conditions for exact recovery of the vertex-variables $x^V$ from the edge-variables $Y^E$. We speak of exact recovery if there is a decoding algorithm that 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 